class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
}
};
100142. 交换得到字典序最小的数组
给你一个下标从 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 <= 1051 <= nums[i] <= 1091 <= limit <= 109原站题解
cpp 解法, 执行用时: 500 ms, 内存消耗: 175.2 MB, 提交时间: 2023-11-26 15:09:46
class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n = nums.size();
typedef pair<int, int> pii;
// 把所有元素从小到大排序，要记录一下原来的下标
vector<pii> vec;
for (int i = 0; i < n; i++) vec.push_back(pii(nums[i], i));
sort(vec.begin(), vec.end());
// 把所有元素切成若干子段，子段内的相邻元素之差不超过 limit
vector<vector<pii>> segs;
int last = -limit;
for (int i = 0; i < n; i++) {
if (vec[i].first - last > limit) segs.push_back({});
segs.back().push_back(vec[i]);
last = vec[i].first;
}
vector<int> ans(n);
// 对每个子段分别从小到大排序，填回序列中
for (auto &seg : segs) {
vector<int> pos;
for (auto &p : seg) pos.push_back(p.second);
sort(pos.begin(), pos.end());
for (int i = 0; i < seg.size(); i++) ans[pos[i]] = seg[i].first;
}
return ans;
}
};
python3 解法, 执行用时: 412 ms, 内存消耗: 41.4 MB, 提交时间: 2023-11-26 15:11:17
class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
c = list(enumerate(nums))
c.sort(key=lambda a: a[1])
n = len(nums)
a = [c[0][0]]
b = [c[0][1]]
i = 1
while i < n:
if c[i][1] - c[i-1][1] <= limit:
a.append(c[i][0])
b.append(c[i][1])
else:
a.sort()
m = len(a)
for j in range(m):
nums[a[j]] = b[j]
a = [c[i][0]]
b = [c[i][1]]
i += 1
a.sort()
m = len(a)
for i in range(m):
nums[a[i]] = b[i]
return nums
java 解法, 执行用时: 104 ms, 内存消耗: 62.5 MB, 提交时间: 2023-11-26 15:11:55
class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int[][] tmp = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
tmp[i][0] = nums[i];
tmp[i][1] = i;
}
Arrays.sort(tmp, (o1, o2) -> o1[0] == o2[0] ? (o1[1] - o2[1]) : (o1[0] - o2[0]));
int[] res = new int[nums.length];
int index = 0;
while (index < tmp.length) {
List<Integer> value = new ArrayList<>();
List<Integer> indexList = new ArrayList<>();
int max = tmp[index][0];
while (index < tmp.length && tmp[index][0] <= max) {
max = tmp[index][0] + limit;
value.add(tmp[index][0]);
indexList.add(tmp[index][1]);
index++;
}
Collections.sort(value);
Collections.sort(indexList);
for (int i = 0; i < indexList.size(); i++) {
res[indexList.get(i)] = value.get(i);
}
}
return res;
}
}