Kimi LeetCode LCP 24. 数字游戏 Java实现

以下是 LeetCode LCP 24. 数字游戏的 Java 实现核心思路是转换 中位数贪心 对顶堆javaclass Solution {private static final int MOD 1_000_000_007;public int[] numsGame(int[] nums) {int n nums.length;int[] ans new int[n];// 转换令 a[i] nums[i] - i// 这样nums[a]1 nums[a1]就等价于a[a] a[a1]// 问题转化为让前i个数相等的最小操作次数绝对值之和最小化// 根据中位数贪心当所有数等于中位数时绝对值之和最小// 大根堆存储较小的一半堆顶是较小一半的最大值PriorityQueueLong left new PriorityQueue((a, b) - Long.compare(b, a));// 小根堆存储较大的一半堆顶是较大一半的最小值即中位数PriorityQueueLong right new PriorityQueue();long sumLeft 0; // 左堆元素之和long sumRight 0; // 右堆元素之和for (int i 0; i n; i) {long x (long) nums[i] - i;// 插入元素if (right.isEmpty() || x right.peek()) {right.offer(x);sumRight x;} else {left.offer(x);sumLeft x;}// 平衡两个堆的大小保证 |left.size() - right.size()| 1// 且 right.size() left.size()中位数在右堆顶if (right.size() left.size() 1) {long val right.poll();sumRight - val;left.offer(val);sumLeft val;} else if (left.size() right.size()) {long val left.poll();sumLeft - val;right.offer(val);sumRight val;}long median right.peek();// 计算操作次数 |所有元素到中位数的距离之和|// (median * left.size() - sumLeft) (sumRight - median * right.size())long cost (median * left.size() - sumLeft) (sumRight - median * right.size());ans[i] (int) (cost % MOD);}return ans;}}核心思路1. 问题转换题目要求将 nums[0..i] 操作成满足 nums[a]1 nums[a1] 的序列。这意味着最终序列形如 x, x1, x2, ..., xi。将每个元素减去其下标a[i] nums[i] - i则条件转化为 a[0] a[1] ... a[i]。问题变为让前 i 个数相等的最小操作次数每次操作可以将某个数 1 或 -1。2. 中位数贪心对于一维数轴上的点使所有点到某点的距离之和最小该点即为中位数。因此目标值应取 a[0..i] 的中位数。3. 对顶堆维护中位数- 左堆大根堆存储较小的一半- 右堆小根堆存储较大的一半堆顶即为中位数- 维护 right.size() left.size()使得中位数始终在右堆顶每次插入新元素后通过调整堆的大小保持平衡然后利用两个堆的元素和快速计算到中位数的距离之和。复杂度- 时间复杂度O(N \log N)每次堆操作 O(\log N)- 空间复杂度O(N)两个堆的空间示例验证以 nums [3,4,5,1,6,7] 为例- 转换后a [3, 3, 3, -2, 2, 2]- i0: [3] → 中位数 3cost0- i1: [3,3] → 中位数 3cost0- i2: [3,3,3] → 中位数 3cost0- i3: [3,3,3,-2] → 中位数 3cost|3-3||3-3||3-3||-2-3|5- i4: 中位数 3cost516-2 变 3 需 5 步2 变 3 需 1 步- i5: 中位数 3cost617输出 [0,0,0,5,6,7] ✓