Description#
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 <= 1051 <= nums[i] <= 1091 <= limit <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
arr = sorted(zip(nums, range(n)))
ans = [0] * n
i = 0
while i < n:
j = i + 1
while j < n and arr[j][0] - arr[j - 1][0] <= limit:
j += 1
idx = sorted(k for _, k in arr[i:j])
for k, (x, _) in zip(idx, arr[i:j]):
ans[k] = x
i = j
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> nums[i] - nums[j]);
int[] ans = new int[n];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
++j;
}
Integer[] t = Arrays.copyOfRange(idx, i, j);
Arrays.sort(t, (x, y) -> x - y);
for (int k = i; k < j; ++k) {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return nums[i] < nums[j];
});
vector<int> ans(n);
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
++j;
}
vector<int> t(idx.begin() + i, idx.begin() + j);
sort(t.begin(), t.end());
for (int k = i; k < j; ++k) {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func lexicographicallySmallestArray(nums []int, limit int) []int {
n := len(nums)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
slices.SortFunc(idx, func(i, j int) int { return nums[i] - nums[j] })
ans := make([]int, n)
for i := 0; i < n; {
j := i + 1
for j < n && nums[idx[j]]-nums[idx[j-1]] <= limit {
j++
}
t := slices.Clone(idx[i:j])
slices.Sort(t)
for k := i; k < j; k++ {
ans[t[k-i]] = nums[idx[k]]
}
i = j
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function lexicographicallySmallestArray(nums: number[], limit: number): number[] {
const n: number = nums.length;
const idx: number[] = Array.from({ length: n }, (_, i) => i);
idx.sort((i, j) => nums[i] - nums[j]);
const ans: number[] = Array(n).fill(0);
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
j++;
}
const t: number[] = idx.slice(i, j).sort((a, b) => a - b);
for (let k: number = i; k < j; k++) {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
return ans;
}
|
