Skip to content

Latest commit

 

History

History
215 lines (169 loc) · 7.24 KB

2948.md

File metadata and controls

215 lines (169 loc) · 7.24 KB
title description keywords
2948. 交换得到字典序最小的数组
LeetCode 2948. 交换得到字典序最小的数组题解，Make Lexicographically Smallest Array by Swapping Elements，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2948. 交换得到字典序最小的数组
交换得到字典序最小的数组
Make Lexicographically Smallest Array by Swapping Elements
解题思路
并查集
数组
排序

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

🟠 Medium  🔖  并查集 数组 排序  🔗 力扣 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 执行交换操作后的最小汉明距离 深度优先搜索 并查集 数组 🟠 🀄️ 🔗