交换后字典序最小数组 —— 排序分组重分配

日期: 2026-08-28

难度: 中等

标签: 排序、分组（连通块）、贪心、字典序

题目链接: [2948. 交换后的字典序最小数组]

题目描述

正整数数组 nums 和正整数 limit。每次操作可选任意两个下标 i、j，若 |nums[i] - nums[j]| ≤ limit 则可交换这两个元素。返回执行任意次操作后能得到的字典序最小数组。

示例：nums = [1,5,3,9,8], limit = 2 → [1,3,5,8,9]
提示：n ≤ 10^5，nums[i] ≤ 10^9

第一次思路

逐位贪心：先排序得到 temp，从前往后扫描，希望每一位都放尽可能小的数：

若 temp[i] == nums[i] 跳过
若 |temp[i] - nums[i]| ≤ limit 直接交换
否则尝试间接交换：找 j > i 使 |temp[j] - nums[i]| ≤ limit 且 |temp[i] - temp[j]| ≤ limit，先换 temp[j] 和 nums[i]，再换 temp[i] 和 temp[j]

// 第一版：直接交换 + 一层间接交换（卡住）
for (int i = 0; i < n; i++) {
    if (temp[i] == nums[i]) continue;
    if (abs(temp[i] - nums[i]) <= limit) { swap(nums, temp[i], nums[i], i); }
    else {
        int pos = -1;
        for (int j = i + 1; j < n; j++) {
            if (abs(temp[j] - nums[i]) <= limit && abs(temp[i] - temp[j]) <= limit) {
                pos = j; break;
            }
        }
        if (pos == -1) continue;  // 找不到就直接跳过
        swap(nums, temp[pos], nums[i], i);
        swap(nums, temp[i], temp[pos], i);
    }
}

问题：间接交换可能不止一层——nums[i] 也许要经过两跳、三跳才能换到位。只试一层就放弃会漏解，但继续枚举所有跳数既复杂又难证贪心正确。这个方向走进了死胡同。

最终方案

关键洞察：把”任意次交换”看成图上的连通性——每个元素是点，差值 ≤ limit 连一条边。能通过一系列交换互达 ⇔ 在同一连通块里：

同一连通块内：可以任意排列（链式交换可达）
不同连通块间：完全隔离（无法交换）

注意陷阱：|a-b| ≤ limit 本身不传递（a≈b、b≈c 推不出 a≈c），但”通过中间值链式交换“是可传递的。所以排序后，只要相邻两个值差 ≤ limit 就在同一块——整段连通。

算法（排序 + 分组 + 重分配）：

temp = sort(nums)
分组：temp[i] - temp[i-1] > limit 则开新块，group[i] 记录块号
值 → 块号映射 valToGroup（重复值排序后连续，天然同块，无需特判）
每块记录在 temp 中的起始下标 start[g]，指针 ptr[g] 从 start[g] 递增
遍历原数组：g = valToGroup[nums[i]]，ans[i] = temp[ptr[g]++]——每块内从最小开始取

正确性：每个位置只能取自己块内的值（块间无法交换）；块内可任意排列，取”块内最小未用值”不损害后续任何选择。从前往后逐位取最小 ⇒ 字典序最小。

完整代码

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());

        // 1. 分组：相邻差值 > limit 断开，形成连通块
        vector<int> group(n);
        int gid = 0;
        group[0] = 0;
        for (int i = 1; i < n; i++) {
            if (sorted[i] - sorted[i - 1] > limit) gid++;
            group[i] = gid;
        }

        // 2. 值 → 块号映射（值域 1e9，用哈希表）
        unordered_map<int, int> valToGroup;
        for (int i = 0; i < n; i++) valToGroup[sorted[i]] = group[i];

        // 3. 每块在 sorted 中的起始下标
        vector<int> start(gid + 1, 0);
        for (int i = 1; i < n; i++) {
            if (group[i] != group[i - 1]) start[group[i]] = i;
        }

        // 4. 遍历原数组，从所属块中依次取最小未用值
        vector<int> ans(n);
        vector<int> ptr = start;
        for (int i = 0; i < n; i++) {
            int g = valToGroup[nums[i]];
            ans[i] = sorted[ptr[g]++];
        }
        return ans;
    }
};

复杂度分析

复杂度	分析
时间复杂度	O(n log n) — 排序 O(n log n)，分组 + 映射 + 构造各 O(n)
空间复杂度	O(n) — sorted / group / 哈希表 / ans

补充：从 block/bp 到 start/ptr 的简化

我第一版 AC 用的是 block（vector<vector<int>> 存每块元素）+ bp（每块剩余数量）+ 从后往前取（block[g][size - bp[g]]）。正确但绕。因为块在排序数组里就是连续的一段，只需记起始下标 + 指针递增：

去掉 block：直接用 sorted 取数
去掉 bp：ptr[g] 从 start[g] 开始自增
三个数组（group / start / ptr）+ 一个哈希表，逻辑更直白