Make Lexicographically Smallest Array by Swapping Elements

You are given a 0-indexed array of positive integers nums and a positive integer limit.

In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.

Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.

Example 1:

Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: Apply the operation 2 times:
- Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
- Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9]
We cannot obtain a lexicographically smaller array by applying any more operations.
Note that it may be possible to get the same result by doing different operations.

Example 2:

Input: nums = [1,7,6,18,2,1], limit = 3
Output: [1,6,7,18,1,2]
Explanation: Apply the operation 3 times:
- Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
- Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
- Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2]
We cannot obtain a lexicographically smaller array by applying any more operations.

Example 3:

Input: nums = [1,7,28,19,10], limit = 3
Output: [1,7,28,19,10]
Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= limit <= 10⁹

解题思路

lc 难得爆零。

看题解都说经典结论题，把序列的每个元素看作是一个点，如果两个点之间可以互换则连一条边。即对于元素 $x$，将 $x$ 与值域在 $[x - \text{limit}, x + \text{limit}]$ 范围内的元素连一条边即可。那么就会形成若干个连通块，每个连通块内的元素可以任意互换，为了让字典序最小只需让每个连通块内的元素递增即可。

剩下的问题就是如何连边，先对数组进行排序，容易想到枚举每个元素，与右边不超过 $x + \text{limit}$ 的元素都连一条边，但最糟糕的情况下时间复杂度会达到 $O(n^2)$。实际上我们只需考虑右边与它相邻的元素即可，即如果 $a_{i+1} - a_i \leq \text{limit}$，那么 $a_i$ 与 $a_{i+1}$ 连边。如果 $a_j - a_i \leq \text{limit}$，那么必然有 $a_j - a_{i+1} \leq \text{limit}$，并且因为连通性 $a_i$ 必然会与 $a_j$ 在同一个连通块。

实际上上面的做法等价于将序列分成连续的若干段，每一段内的元素都有 $a_{i+1} - a_i \leq \text{limit}$。我们只需找出这样的每一段即可。

AC 代码如下，时间复杂度为 $O(n \log{n})$：

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int i, int j) {
            return nums[i] < nums[j];
        });
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int j = i;
            set<int> st({p[i]});
            while (i + 1 < n && nums[p[i + 1]] - nums[p[i]] <= limit) {
                st.insert(p[++i]);
            }
            auto it = st.begin();
            for (int k = j; k <= i; k++, it++) {
                ans[*it] = nums[p[k]];
            }
        }
        return ans;
    }
};