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边缘控制无人机在地下矿山的实战部署

更多资讯

amis Calendar 日历日程组件完全指南：从日程配置到事件动作的 JSON 实战

Tabler Icons SVG Sprite 完整指南：安装、使用与源码级构建原理

Kubespray 镜像加速实战：用 *_image_repo 与 files_repo 变量配置公共下载镜像

Refine v5 + Chakra UI Breadcrumb 组件详解：面包屑导航的接入、定制与源码原理

No such file or directory 报错排查手册：从原理到实战

蚁群算法在物流调度VRPTW中的Matlab实现与优化

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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