Leetcode 2948. Make Lexicographically Smallest Array by Swapping Elements

• Leetcode 2948. Make Lexicographically Smallest Array by Swapping Elements
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2948. Make Lexicographically Smallest Array by Swapping Elements

1. 解题思路

这一题其实思路上就是分组排序，显然，对于一系列元素，只要满足对任意元素，存在其他某一元素与其差值在limit之内，那么最终我们总能对这些元素在若干次排序后实现有序排列。

因此，我们只需要对原始的元素进行分组，然后分别进行排序即可。

2. 代码实现

给出python代码实现如下：

class Solution:def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:n = len(nums)nums = [(x, i) for i, x in enumerate(nums)]nums = sorted(nums)ans = [0 for _ in range(n)]idx = 0while idx < n:rb = idx+1while rb<n and nums[rb][0] - nums[rb-1][0] <= limit:rb += 1locs = sorted(x[1] for x in nums[idx:rb])for (val, _), i in zip(nums[idx:rb], locs):ans[i] = validx = rbreturn ans

提交代码评测得到：耗时1193ms，占用内存40.6MB。