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

LCP 24. 数字游戏 — JavaScript 实现核心思路问题转化将 nums[0..i] 变为公差为 1 的等差数列 x, x1, ..., xi最小操作次数为\sum{j0}^{i} |nums[j] - (xj)| \sum{j0}^{i} |(nums[j]-j) - x|令 b[j] nums[j] - j问题转化为求 x 使得 Σ|b[j] - x| 最小。数学结论使绝对值之和最小的 x 是数组 b 的中位数。算法用对顶堆动态维护中位数并同时维护两堆元素之和以 O(1) 计算当前操作次数。---完整代码可直接提交javascript/*** LCP 24. 数字游戏* 对顶堆双堆动态维护中位数* param {number[]} nums* return {number[]}*/var numsGame function(nums) {const MOD 1_000_000_007;const n nums.length;const res new Array(n);// 大根堆存储较小的一半包含中位数堆顶即中位数const left new Heap((a, b) b - a);// 小根堆存储较大的一半const right new Heap((a, b) a - b);let sumL 0; // left 堆元素之和let sumR 0; // right 堆元素之和for (let i 0; i n; i) {const val nums[i] - i; // 关键转化// 1. 插入元素if (left.size() 0 || val left.top()) {left.push(val);sumL val;// 平衡left 最多比 right 多 1 个if (left.size() right.size() 1) {const v left.pop();right.push(v);sumL - v;sumR v;}} else {right.push(val);sumR val;// 平衡right 不能比 left 多if (right.size() left.size()) {const v right.pop();left.push(v);sumR - v;sumL v;}}// 2. 中位数const mid left.top();const lc left.size();const rc right.size();// 3. 计算操作次数// left 部分mid 比 left 中所有元素大或等贡献 lc * mid - sumL// right 部分right 中所有元素比 mid 大贡献 sumR - rc * midconst partL BigInt(lc) * BigInt(mid) - BigInt(sumL);const partR BigInt(sumR) - BigInt(rc) * BigInt(mid);let ans Number((partL partR) % BigInt(MOD));if (ans 0) ans MOD;res[i] ans;}return res;};/* 自定义堆优先队列 */class Heap {constructor(compare) {this.data [];this.compare compare; // 返回负数表示 a 应在 b 前面}size() {return this.data.length;}top() {return this.data[0];}push(val) {this.data.push(val);this._up(this.data.length - 1);}pop() {if (this.data.length 1) return this.data.pop();const top this.data[0];this.data[0] this.data.pop();this._down(0);return top;}_up(i) {while (i 0) {const p (i - 1) 1;if (this.compare(this.data[i], this.data[p]) 0) break;[this.data[i], this.data[p]] [this.data[p], this.data[i]];i p;}}_down(i) {const n this.data.length;while (true) {let l i * 2 1, r i * 2 2, minIdx i;if (l n this.compare(this.data[l], this.data[minIdx]) 0) minIdx l;if (r n this.compare(this.data[r], this.data[minIdx]) 0) minIdx r;if (minIdx i) break;[this.data[i], this.data[minIdx]] [this.data[minIdx], this.data[i]];i minIdx;}}}---关键点说明步骤 说明nums[i] - i 将公差为 1 的等差数列条件转化为所有元素相等中位数最优 Σ\|b[j] - x\| 在 x 取中位数时最小对顶堆 left大根堆存较小一半right小根堆存较大一半始终保持 left.size() right.size() 或 left.size() right.size() 1O(1) 求答案 利用两堆的和 sumL、sumR直接公式计算总距离无需遍历复杂度- 时间O(n log n)每个元素最多两次堆操作- 空间O(n)两堆共存储 n 个元素