题目描述

给你一个下标从 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。

样例

输入：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]。
即便执行更多次操作，也无法得到字典序更小的数组。
注意，执行不同的操作也可能会得到相同的结果。

输入：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]。
即便执行更多次操作，也无法得到字典序更小的数组。

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

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= limit <= 10^9

算法

(思维题) $O(n \log n)$

1. 注意到，我们可以按照 $limit$ 将数组划分为若干个互不相交的组，满足每个组内不存在某个数字，使得其与其他数字的差值都超过 $limit$。也就是说，每个组内都可以通过交换，达到任意排序的目的。
2. 首先从小到大排序数组，排序后就可以很容易的划分组。此时可以得到每个组内的下标，接着将每个组在原数组的下标中排序，并按顺序放回到原数组的下标中。

时间复杂度

• 排序后，对于每一组还会再单独排序下标。故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序的系统栈和答案。

C++ 代码

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        const int n = nums.size();

        vector<int> id(n);
        for (int i = 0; i < n; i++)
            id[i] = i;

        sort(id.begin(), id.end(), [&](int x, int y) {
            return nums[x] < nums[y];
        });

        vector<int> ans(n);

        int j = 0;
        vector<int> t;
        t.push_back(id[0]);
        for (int i = 1; i <= n; i++) {
            if (i == n || nums[id[i]] - nums[id[i - 1]] > limit) {
                sort(t.begin(), t.end());
                for (int k = j; k < i; k++)
                    ans[t[k - j]] = nums[id[k]];

                t.clear();
                j = i;
            }
            if (i < n)
                t.push_back(id[i]);
        }

        return ans;
    }
};