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

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 <= 105
• 1 <= nums[i] <= 109
• 1 <= limit <= 109

/*
 * 思路：
 * 1. 使用贪心算法，从左到右遍历数组。
 * 2. 每次尽可能交换当前数字和之后尽量小的符合条件的数字。
 * 3. 使用TreeSet来维持一个窗口，用于快速找到可以交换的最小元素。
 * 4. 使用Java Streams来实现。
 */
import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int[] minLexicoArray(int[] nums, int limit) {
        TreeSet<Integer> set = new TreeSet<>();
        IntStream.range(0, nums.length).forEach(i -> {
            set.add(nums[i]);
            Integer minInRange = set.ceiling(nums[i] - limit);
            if (minInRange != null && minInRange <= nums[i] + limit) {
                set.remove(minInRange);
                set.add(nums[i]);
                nums[i] = minInRange;
            }
        });
        return nums;
    }
}

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

O(n log n)

O(n)