交换得到字典序最小的数组

标签: 并查集 数组 排序

难度: Medium

给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。

在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 |nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。

返回执行任意次操作后能得到的 字典序最小的数组 。

如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应元素比数组 b 中的对应元素的字典序更小，则认为数组 a 就比数组 b 字典序更小。例如，数组 [2,10,3] 比数组 [10,2,3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。

示例 1：

输入：nums = [1,5,3,9,8], limit = 2
输出：[1,3,5,8,9]
解释：执行 2 次操作：
- 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。
- 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。
即便执行更多次操作，也无法得到字典序更小的数组。
注意，执行不同的操作也可能会得到相同的结果。

示例 2：

输入：nums = [1,7,6,18,2,1], limit = 3
输出：[1,6,7,18,1,2]
解释：执行 3 次操作：
- 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。
- 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。
- 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。
即便执行更多次操作，也无法得到字典序更小的数组。

示例 3：

输入：nums = [1,7,28,19,10], limit = 3
输出：[1,7,28,19,10]
解释：[1,7,28,19,10] 是字典序最小的数组，因为不管怎么选择下标都无法执行操作。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= limit <= 109

Submission

运行时间: 232 ms

内存: 35.4 MB

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        idx = [v for v in range(n)]
        idx.sort(key=lambda b: nums[b])
        t = []
        ans = [0] * n
        for i in range(n):
            if i == 0 or nums[idx[i]] - nums[idx[i - 1]] <= limit:
                t.append(idx[i])
            else:
                for j, k in zip(t, sorted(t)):
                    ans[k] = nums[j]
                t = [idx[i]]
        for j, k in zip(t, sorted(t)):
            ans[k] = nums[j]
        return ans

Explain

这个题解的思路是首先对数组中的元素按照其值的大小进行索引排序，以确定字典序的顺序。然后，利用limit条件来确定哪些元素可以彼此交换。通过检查相邻元素的差是否小于或等于limit，可以将整个数组分割成若干组，每组内的元素都可以任意交换。因此，每组内部按照原始索引进行排序，然后将组内元素按原始顺序填充到结果数组中，以确保每组内部元素在结果数组中的顺序是字典序最小的。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        idx = [v for v in range(n)]
        # 对索引按照对应的nums值排序
        idx.sort(key=lambda b: nums[b])
        t = []
        ans = [0] * n
        for i in range(n):
            if i == 0 or nums[idx[i]] - nums[idx[i - 1]] <= limit:
                # 当前元素与前一个元素的差在limit范围内，可以加入当前分组
                t.append(idx[i])
            else:
                # 超过limit，前一个分组结束，按照原索引顺序填充结果数组
                for j, k in zip(t, sorted(t)):
                    ans[k] = nums[j]
                t = [idx[i]]
        # 处理最后一个分组
        for j, k in zip(t, sorted(t)):
            ans[k] = nums[j]
        return ans

Explore

这一步的主要目的是为了确定哪些元素可以交换以达到字典序最小化的目的。通过按值大小对索引进行排序，我们可以直观地看到元素按照字典序排列的顺序，从而在接下来的步骤中更容易分组和判断哪些元素可以在给定的limit条件下交换。排序后的索引数组将帮助我们理解在不违反交换限制的情况下，数组可以如何通过交换操作达到字典序最小。

哪些元素可以组成一组是基于它们之间的差值是否小于或等于limit来决定的。具体来说，当我们按照元素值排序索引后，会检查连续的元素（按排序后的顺序）之间的差值。如果这个差值小于或等于limit，这意味着这两个元素可以交换位置，因此它们可以放在同一组中。通过这种方式，连续的符合条件的元素就会被划分为同一组，每一组内的元素可以自由交换以达到该组内字典序最小。

首先对元素按值进行排序是为了确定可以互换的元素，并将它们分组。每个组内部再按原始索引排序的原因是为了保证在最终的数组中，每个组内的元素顺序是按照原始顺序出现的，这样可以确保在满足交换条件下，组内的元素顺序是最小字典序。这种方法的优势在于，它不仅考虑了元素值的排序，还保持了元素的相对位置，从而确保了最终结果的一致性和正确性。

这种情况是有可能发生的。在题解中提到的方法采用了连续性的分组逻辑，即只有当元素连续且差值不超过limit时才划分为同一组。这可能导致跳跃式的元素组合（例如，索引更远的元素对在limit范围内）不能被考虑到，因此这种策略可能不是全局最优的。在极端情况下，可能会有更好的分组方法能够进一步减小最终数组的字典序，但这将需要更复杂的算法来实现。