Kimi LeetCode 3505. 使 K 个子数组内元素相等的最少操作数 Java实现-北京尧图网络

以下是 LeetCode 3505. 使 K 个子数组内元素相等的最少操作数的 Java 实现---思路概述本题是 LeetCode 462最小操作次数使数组元素相等 II和 LeetCode 480滑动窗口中位数的结合题。核心思路1. 中位数贪心对于一个子数组要使其所有元素相等且操作次数最少最终值应取子数组的中位数。证明可参考 LeetCode 462。2. 滑动窗口中位数用对顶堆两个 TreeMap 模拟堆延迟删除策略维护长度为 x 的滑动窗口快速求出每个窗口变为相等的最小操作次数 cost[i]。3. 划分型 DPdp[i][j] 表示前 i 个元素中选出 j 个不重叠的长度为 x 的子数组的最小操作数。- 不选dp[i][j] dp[i-1][j]- 选以 i-1 结尾的子数组dp[i][j] dp[i-x][j-1] cost[i-1]---完整 Java 代码javaimport java.util.*;class Solution {// 对顶堆延迟删除维护滑动窗口中位数// 参考 LeetCode 480. 滑动窗口中位数和 462. 最小操作次数使数组元素相等 IIstatic class DualHeap {// small: 大根堆存放较小的一半元素// large: 小根堆存放较大的一半元素中位数在堆顶private TreeMapInteger, Integer small;private TreeMapInteger, Integer large;private int smallSize, largeSize; // 实际有效元素个数private long smallSum, largeSum; // 元素之和private MapInteger, Integer delayed; // 延迟删除的哈希表private int smallTarget, largeTarget; // 目标大小public DualHeap(int k) {small new TreeMap(Collections.reverseOrder()); // 大根堆large new TreeMap(); // 小根堆delayed new HashMap();// small 放 floor(k/2) 个large 放 ceil(k/2) 个// 这样中位数就是 large.firstKey()smallTarget k / 2;largeTarget k - smallTarget;}// 插入元素public void insert(int num) {if (small.isEmpty() || num small.firstKey()) {small.merge(num, 1, Integer::sum);smallSum num;smallSize;} else {large.merge(num, 1, Integer::sum);largeSum num;largeSize;}makeBalance();}// 删除元素延迟删除public void erase(int num) {delayed.merge(num, 1, Integer::sum);if (!small.isEmpty() num small.firstKey()) {smallSize--;smallSum - num;if (num small.firstKey()) {pruneSmall();}} else {largeSize--;largeSum - num;if (!large.isEmpty() num large.firstKey()) {pruneLarge();}}makeBalance();}// 获取中位数large 的最小元素public int getMedian() {return large.firstKey();}// 计算当前窗口变为全部相等中位数所需的操作次数public long getCost() {int median getMedian();// small 中的元素需要增加到 medianlong cost1 (long) median * smallSize - smallSum;// large 中的元素需要减少到 medianlong cost2 largeSum - (long) median * largeSize;return cost1 cost2;}// 平衡两个堆的大小private void makeBalance() {// small 太大将最大元素移到 largeif (smallSize smallTarget) {int num small.firstKey();int cnt small.get(num);if (cnt 1) small.remove(num);else small.put(num, cnt - 1);smallSum - num;smallSize--;large.merge(num, 1, Integer::sum);largeSum num;largeSize;pruneSmall();}// large 太大将最小元素移到 smallelse if (largeSize largeTarget) {int num large.firstKey();int cnt large.get(num);if (cnt 1) large.remove(num);else large.put(num, cnt - 1);largeSum - num;largeSize--;small.merge(num, 1, Integer::sum);smallSum num;smallSize;pruneLarge();}}// 清理 small 堆顶的延迟删除元素private void pruneSmall() {while (!small.isEmpty()) {int num small.firstKey();if (delayed.getOrDefault(num, 0) 0) {delayed.put(num, delayed.get(num) - 1);if (delayed.get(num) 0) delayed.remove(num);int cnt small.get(num);if (cnt 1) small.remove(num);else small.put(num, cnt - 1);} else {break;}}}// 清理 large 堆顶的延迟删除元素private void pruneLarge() {while (!large.isEmpty()) {int num large.firstKey();if (delayed.getOrDefault(num, 0) 0) {delayed.put(num, delayed.get(num) - 1);if (delayed.get(num) 0) delayed.remove(num);int cnt large.get(num);if (cnt 1) large.remove(num);else large.put(num, cnt - 1);} else {break;}}}}public long minOperations(int[] nums, int x, int k) {int n nums.length;long INF (long) 1e18;// Step 1: 预处理 cost[i]// cost[i] 表示子数组 nums[i-x1..i]长度为x全部变为相等的最小操作数long[] cost new long[n];Arrays.fill(cost, INF);DualHeap dh new DualHeap(x);// 初始化第一个窗口 [0, x-1]for (int i 0; i x; i) {dh.insert(nums[i]);}cost[x - 1] dh.getCost();// 滑动窗口for (int i x; i n; i) {dh.insert(nums[i]); // 右端加入新元素dh.erase(nums[i - x]); // 左端删除旧元素cost[i] dh.getCost();}// Step 2: 动态规划// dp[i][j] 考虑前 i 个元素0..i-1选出 j 个不重叠的长度为x的子数组的最小操作数// 转移// 1. 不选以 i-1 结尾的子数组: dp[i][j] dp[i-1][j]// 2. 选以 i-1 结尾的子数组: dp[i][j] dp[i-x][j-1] cost[i-1]long[][] dp new long[n 1][k 1];for (int i 0; i n; i) {Arrays.fill(dp[i], INF);}dp[0][0] 0;for (int i 1; i n; i) {for (int j 0; j k; j) {// 情况1: 不选以 i-1 为结尾的子数组dp[i][j] dp[i - 1][j];// 情况2: 选以 i-1 为结尾的子数组if (i x j 1 cost[i - 1] INF) {dp[i][j] Math.min(dp[i][j], dp[i - x][j - 1] cost[i - 1]);}}}return dp[n][k];}}---复杂度分析项目复杂度时间 O(n log x · k) — 滑动窗口 O(n log x)DP O(nk)空间 O(n x nk) — cost 数组 O(n)对顶堆 O(x)DP 数组 O(nk)由于 k ≤ 15nk 最大约为 1.5 × 10⁶空间可接受。---下载链接[LeetCode3505.java](sandbox:///mnt/agents/output/LeetCode3505.java)

Kimi LeetCode 3505. 使 K 个子数组内元素相等的最少操作数 Java实现

相关推荐

TB6593FNG与PIC18F86J50的直流电机控制方案详解

Gemini 3.5 Flash：软硬协同的低延迟推理架构解析

5G边缘控制无人机在地下矿山的实战部署

更多资讯

伊滨区电工证培训机构怎么选？通过率揭秘别再交冤枉钱

小希叉车特种工网上查询怎么操作？别再被中介坑了

武汉电工证注册多少钱保姆级教程：实操考试心里没底怕挂科怎么办

梦见电工证过期了不知道怎么复审延期？全国通用的电工证怎么查？

增城新能源电工证怕考不过白交培训费？网上查询全攻略来了

廊坊本地考电工证多久拿证实操考试心里没底怕挂科

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？