Medium

题目描述

给你一个下标从 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. 构建连通性图：两个元素 nums[i] 和 nums[j] 如果满足 |nums[i] - nums[j]| <= limit，则它们可以交换。这实际上构成了一个图，其中节点是数组元素，边表示可以交换的关系。

  2. 寻找连通分量：我们需要找出所有的连通分量。在同一个连通分量内的元素可以通过一系列交换操作达到任意排列。

  3. 排序优化：关键观察是，先将数组排序后，只需要检查相邻元素是否可以交换即可确定连通分量。因为如果 a 和 c 都能与 b 交换，且 a < b < c，那么 a 和 c 就在同一连通分量中。

  4. 贪心策略：为了得到字典序最小的数组，我们从左到右遍历原数组的每个位置，对于每个位置，从其所属连通分量中选择当前最小的元素放置。

算法步骤：

  • 创建索引数组并按元素值排序
  • 使用并查集或者直接分组找出连通分量
  • 对每个连通分量内的元素排序
  • 贪心地为每个位置分配最小可用元素

代码实现

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        
        // 按元素值排序索引
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return nums[i] < nums[j];
        });
        
        // 找连通分量
        vector<vector<int>> groups;
        vector<int> groupId(n);
        
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[indices[i]] - nums[indices[i-1]] > limit) {
                groups.push_back({});
            }
            groups.back().push_back(indices[i]);
            groupId[indices[i]] = groups.size() - 1;
        }
        
        // 为每个组准备排序后的值
        vector<queue<int>> groupValues(groups.size());
        for (int i = 0; i < groups.size(); i++) {
            vector<int> values;
            for (int idx : groups[i]) {
                values.push_back(nums[idx]);
            }
            sort(values.begin(), values.end());
            for (int val : values) {
                groupValues[i].push(val);
            }
        }
        
        // 贪心分配
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            int gId = groupId[i];
            result[i] = groupValues[gId].front();
            groupValues[gId].pop();
        }
        
        return result;
    }
};

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        indices = list(range(n))
        
        # 按元素值排序索引
        indices.sort(key=lambda i: nums[i])
        
        # 找连通分量
        groups = []
        group_id = [0] * n
        
        for i in range(n):
            if i == 0 or nums[indices[i]] - nums[indices[i-1]] > limit:
                groups.append([])
            groups[-1].append(indices[i])
            group_id[indices[i]] = len(groups) - 1
        
        # 为每个组准备排序后的值
        group_values = []
        for group in groups:
            values = sorted([nums[idx] for idx in group])
            group_values.append(values)
        
        # 贪心分配
        result = [0] * n
        group_pointers = [0] * len(groups)
        
        for i in range(n):
            gid = group_id[i]
            result[i] = group_values[gid][group_pointers[gid]]
            group_pointers[gid] += 1
        
        return result

public class Solution {
    public int[] LexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.Length;
        var indices = Enumerable.Range(0, n).ToArray();
        
        // 按元素值排序索引
        Array.Sort(indices, (i, j) => nums[i].CompareTo(nums[j]));
        
        // 找连通分量
        var groups = new List<List<int>>();
        var groupId = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[indices[i]] - nums[indices[i-1]] > limit) {
                groups.Add(new List<int>());
            }
            groups[groups.Count - 1].Add(indices[i]);
            groupId[indices[i]] = groups.Count - 1;
        }
        
        // 为每个组准备排序后的值
        var groupValues = new List<Queue<int>>();
        for (int i = 0; i < groups.Count; i++) {
            var values = groups[i].Select(idx => nums[idx]).OrderBy(x => x).ToList();
            var queue = new Queue<int>(values);
            groupValues.Add(queue);
        }
        
        // 贪心分配
        var result = new int[n];
        for (int i = 0; i < n; i++) {
            int gId = groupId[i];
            result[i] = groupValues[gId].Dequeue();
        }
        
        return result;
    }
}

var lexicographicallySmallestArray = function(nums, limit) {
    const n = nums.length;
    const indexedNums = nums.map((val, idx) => [val, idx]);
    indexedNums.sort((a, b) => a[0] - b[0]);
    
    const groups = [];
    let currentGroup = [indexedNums[0]];
    
    for (let i = 1; i < n; i++) {
        if (indexedNums[i][0] - indexedNums[i-1][0] <= limit) {
            currentGroup.push(indexedNums[i]);
        } else {
            groups.push(currentGroup);
            currentGroup = [indexedNums[i]];
        }
    }
    groups.push(currentGroup);
    
    const result = new Array(n);
    
    for (const group of groups) {
        const values = group.map(item => item[0]);
        const indices = group.map(item => item[1]).sort((a, b) => a - b);
        values.sort((a, b) => a - b);
        
        for (let i = 0; i < indices.length; i++) {
            result[indices[i]] = values[i];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)
空间复杂度O(n)

时间复杂度主要来自排序操作，分组和贪心分配都是线性时间。空间复杂度用于存储索引数组、分组信息和结果数组。

相关题目