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

🟠   🔖  并查集 数组 排序  🔗 力扣 LeetCode

题目

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^5
• 1 <= nums[i] <= 10^9
• 1 <= limit <= 10^9

题目大意

给你一个下标从 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 <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= limit <= 10^9

解题思路

1. 对数组的值及索引进行处理：

   • 用数组 sorted 存储每个数字及其原始索引。
   • 按照值从小到大排序。

2. 分组：

   • 遍历排序后的数组，检查相邻数字是否满足差值不超过 limit。
   • 如果差值满足条件，将其加入当前分组；否则，开启一个新的分组。

3. 组内处理：

   • 对每一组，按照原始索引对分组重新排序。
   • 对分组内的值重新按字典序排序。
   • 将排序后的值放回对应位置。

4. 返回结果：

   • 最终返回调整后的数组。

复杂度分析

• 时间复杂度： O(n log n)
  • 对 nums 排序的时间复杂度为 O(n log n)。
  • 分组的复杂度为 O(n)。
  • 每组排序的复杂度为 O(k log k)，k 是分组内元素的数量，总复杂度接近 O(n log n)。
  • 总复杂度为 O(n log n)
• 空间复杂度：O(n)，存储分组及结果。

代码

/**
 * @param {number[]} nums
 * @param {number} limit
 * @return {number[]}
 */
var lexicographicallySmallestArray = function (nums, limit) {
	const n = nums.length;
	// 排序时保留原始索引
	const sorted = nums.map((num, i) => [num, i]).sort((a, b) => a[0] - b[0]);

	// 分组
	const groups = [];
	let cur = [sorted[0]];
	for (let i = 1; i < n; i++) {
		if (sorted[i][0] - sorted[i - 1][0] <= limit) {
			cur.push(sorted[i]);
		} else {
			groups.push(cur);
			cur = [sorted[i]];
		}
	}
	groups.push(cur); // 添加最后一组

	// 构建结果数组
	const res = new Array(n);

	// 对每一组排序并放回原位
	for (let group of groups) {
		// 按照原始索引排序
		group.sort((a, b) => a[1] - b[1]);
		// 提取当前组的值并排序
		const vals = group.map((i) => i[0]).sort((a, b) => a - b);
		// 将排序后的值填回原位置
		for (let i = 0; i < group.length; i++) {
			res[group[i][1]] = vals[i];
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1202	交换字符串中的元素		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
1722	执行交换操作后的最小汉明距离		深度优先搜索 并查集 数组	🟠	🀄️ 🔗