LeetCode 题解工作台
交换得到字典序最小的数组
给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。 在一次操作中，你可以选择任意两个下标 i 和 j ， 如果 满足 |nums[i] - nums[j]| ，则交换 nums[i] 和 nums[j] 。 返回执行任意次操作后能得到的 字典序最小的数组 。 如果在数…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 并查集
答案摘要
根据题目描述，排序后的数组 可以划分成若干个子数组，使得每个子数组中的相邻元素之差不超过 。 那么，可以通过交换得到的字典序最小的数组就是将每个子数组中的元素排序后，依次填入原数组所在位置得到的数组。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给你一个下标从 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
解题思路
方法一：排序
根据题目描述，排序后的数组 可以划分成若干个子数组，使得每个子数组中的相邻元素之差不超过 。
那么，可以通过交换得到的字典序最小的数组就是将每个子数组中的元素排序后，依次填入原数组所在位置得到的数组。
我们首先将数组 中的元素和它们的下标组成一个二元组数组，并按照元素的值进行排序。然后，我们遍历排序后的二元组数组，找到每个子数组的范围，并将子数组中的元素按照下标进行排序后，填入原数组所在位置得到最终的结果。
时间复杂度 ，空间复杂度 ，其中 是数组 的长度。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \cdot \log N) |
| 空间 | O(N + S_N) \approx O(N) |
面试官常问的追问
外企场景- question_mark
Check if the candidate can correctly implement Union Find and sort the connected components.
- question_mark
Evaluate their understanding of the problem by asking how they'd handle edge cases, such as when no swaps are possible.
- question_mark
Test their ability to explain and optimize the approach in terms of time and space complexity.
常见陷阱
外企场景- error
Not using Union Find correctly, leading to incorrect grouping of swappable elements.
- error
Failing to sort each group independently after identifying the connected components.
- error
Overcomplicating the solution by trying to perform swaps directly without first sorting the connected components.
进阶变体
外企场景- arrow_right_alt
Change the swap condition to allow only certain elements to be swapped (e.g., based on parity or value range).
- arrow_right_alt
Extend the problem to handle arrays with negative numbers or arrays of arbitrary size.
- arrow_right_alt
Incorporate a step to track the number of swap operations or enforce a limited number of swaps.