今日题目

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/description/

解题思路

  • 本题本质上是一个排序过程，但只有差值小于 limit 的元素才能互相交换。
  • 因此，元素之间会形成若干"分组"。同一组内，相邻元素的差值小于 limit。
  • 对每个分组内的元素单独排序，即可得到最终答案。

解题步骤

  1. 找出所有分组。
  2. 先对数组整体排序。
  3. 若相邻两个数的差值超过 limit，则它们属于不同的分组。
  4. 对每个分组内的结果分别排序。

复杂度分析

  • 时间复杂度：$O(N\times log(N))$，N 为数组长度。

  • 空间复杂度：$O(N)$

代码

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        sorted_nums = []
        for idx, x in enumerate(nums):
            sorted_nums.append((x, idx))
        sorted_nums.sort()

        # First we sort the array
        
        groups = []
        tmp = []
        for i in range(len(nums)):
            if i > 0 and sorted_nums[i][0] - sorted_nums[i-1][0] > limit:
                tmp.sort()
                groups.append(tmp)
                tmp = []

            tmp.append(sorted_nums[i][1])
        
        tmp.sort()
        groups.append(tmp)

        # Then we form groups

        idx = 0
        pos = 0
        ans = [0] * len(nums)
        for i in range(len(nums)):
            if pos == len(groups[idx]):
                pos = 0
                idx += 1

            ans[groups[idx][pos]] = sorted_nums[i][0]
            pos += 1

        # Then we sort the groups
        
        return ans