求使数组所有元素唯一的最小成本的高效正确解法

求使数组所有元素唯一的最小成本的高效正确解法 #

核心思路 #

因为题目规定只能对元素进行递增操作，要实现所有元素唯一且总代价最小，核心逻辑是：让单位增量成本高的元素尽可能少递增（甚至不递增），而让成本低的元素承担更多增量——毕竟成本高的元素每多增1，总代价上涨更快，优先保留它们的原数值更划算。

具体步骤 #

1. 配对并排序：把每个元素和对应的增量成本组成(数值, 成本)二元组，然后按成本从大到小排序；如果成本相同，则按数值从小到大排序（相同成本下，数值小的优先保留原位置）。
2. 并查集维护可用位置：用并查集（Union-Find）高效查找当前元素能使用的最小可用数值（必须≥原数值且未被占用）。并查集的作用是快速定位下一个可用数值，避免重复遍历浪费时间。
3. 计算总代价：遍历排序后的二元组，找到每个元素的可用最小数值，计算该元素的递增代价并累加；之后通过并查集把该数值标记为已占用（合并到下一个数值）。

并查集实现细节 #

并查集需要两个核心操作：

• 查找（Find）：找到≥给定数值的最小可用值。如果当前数值未被占用，直接返回自身；否则递归查找其父节点（即下一个可用数值），同时做路径压缩优化，加快后续查询速度。
• 合并（Union）：当一个数值被占用后，把它和下一个数值合并，这样下次查询该数值时，会直接跳转到下一个可用数值。

由于数值范围可达1e9，我们用哈希表动态存储父节点，无需预先初始化所有可能的数值。

示例验证 #

拿题目中的例子来说：

• 原数组：nums = [3,7,9,7,8]，cost = [5,2,5,7,5]
• 配对后得到：[(3,5), (7,2), (9,5), (7,7), (8,5)]
• 按规则排序后：[(7,7), (3,5), (8,5), (9,5), (7,2)]
• 遍历处理：
  1. (7,7)：找到可用数值7，代价0，标记7已占用，下一个可用数值为8。
  2. (3,5)：找到可用数值3，代价0，标记3已占用，下一个可用数值为4。
  3. (8,5)：找到可用数值8，代价0，标记8已占用，下一个可用数值为9。
  4. (9,5)：找到可用数值9，代价0，标记9已占用，下一个可用数值为10。
  5. (7,2)：查找7的可用数值，经过并查集跳转后得到10，代价(10-7)*2=6，总代价累加为6。

最终总代价为6，和题目示例一致。

时间复杂度分析 #

• 排序的时间复杂度是O(n log n)，这是主要的时间开销。
• 并查集的查找、合并操作经过路径压缩和按秩合并优化后，近似O(1)，遍历数组的时间为O(n)。
• 整体时间复杂度为O(n log n)，完全满足n <= 1e5的约束要求。

伪代码实现（Java风格） #

import java.util.*;

public class MinCostToDistinct {
    static class Pair {
        long num;
        int cost;
        Pair(long num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }

    private Map<Long, Long> parent = new HashMap<>();

    private long find(long x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            return x;
        }
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public long minCost(int[] nums, int[] cost) {
        int n = nums.length;
        Pair[] pairs = new Pair[n];
        for (int i = 0; i < n; i++) {
            pairs[i] = new Pair(nums[i], cost[i]);
        }
        // 按成本降序排序，成本相同则按数值升序
        Arrays.sort(pairs, (a, b) -> {
            if (a.cost != b.cost) {
                return Integer.compare(b.cost, a.cost);
            } else {
                return Long.compare(a.num, b.num);
            }
        });

        long totalCost = 0;
        for (Pair p : pairs) {
            long available = find(p.num);
            totalCost += (available - p.num) * p.cost;
            // 合并当前可用值和下一个值
            long next = find(available + 1);
            parent.put(available, next);
        }
        return totalCost;
    }

    public static void main(String[] args) {
        MinCostToDistinct sol = new MinCostToDistinct();
        int[] nums = {3,7,9,7,8};
        int[] cost = {5,2,5,7,5};
        System.out.println(sol.minCost(nums, cost)); // 输出6
    }
}

备注：内容来源于stack exchange，提问作者CodeCrusader