Kimi LeetCode 3510. 移除最小数对使数组有序 II Python3实现-北京尧图网络

以下是 LeetCode 3510. Minimum Pair Removal to Sort Array II 的 Python3 实现。解题思路这道题要求将时间复杂度从 O(n²) 优化到 O(n log n)核心思路是1. 最小相邻对查找使用最小堆 (heapq) 维护所有相邻元素对的和支持 O(log n) 的插入和弹出最小值。2. 有序性判断不每次扫描整个数组而是维护一个 num_descending 计数器记录当前有多少对相邻元素是递减的即 nums[i] nums[i1]。当计数器为 0 时数组即为非递减序列。3. 双向链表使用 Node 类模拟双向链表实现 O(1) 的节点删除操作。合并两个节点时只需修改指针无需实际移动数组元素。4. 惰性删除堆中可能包含过期的相邻对信息因为某些节点已被合并弹出时检查 node.value node.next.value value不匹配则跳过。Python3 代码pythonimport heapqfrom typing import Listclass Node:def __init__(self, value: int, i: int):self.value value # 当前节点的值self.i i # 原始下标用于打破平局选最左边的对self.prev None # 前一个节点self.next None # 后一个节点self.descending False # 当前节点值下一个节点值def remove(self):从双向链表中移除当前节点if self.prev:self.prev.next self.nextif self.next:self.next.prev self.prevself.next self.prev Noneclass Solution:def minimumPairRemoval(self, nums: List[int]) - int:n len(nums)if n 1:return 0# 初始化双向链表从右往左构建tail Node(nums[-1], n - 1)for i in range(n - 2, -1, -1):head Node(nums[i], i)head.next tailtail.prev headtail head# 初始化最小堆存储 (相邻对和, 左端点原始下标, 左端点节点引用)heap []num_descending 0cur tailwhile cur and cur.next:heap.append((cur.value cur.next.value, cur.i, cur))cur.descending cur.value cur.next.valueif cur.descending:num_descending 1cur cur.nextif num_descending 0:return 0heapq.heapify(heap)num_operations 0while num_descending 0:value, _, node heapq.heappop(heap)# 惰性删除检查这对是否仍然有效# 如果 node 已被合并没有 next或者和已改变则跳过if not node.next or node.value node.next.value ! value:continue# 合并 node 和 node.next# 1. 处理 node.next 的 descending 标记if node.next.descending:num_descending - 1# 2. 移除 node.next 节点node.next.remove()# 3. 更新 node 的值为两数之和node.value valuenum_operations 1# 4. 更新与 node 相关的相邻对前一个和当前节点for pair in (node.prev, node):if not pair:continuedescending Falseif pair.next:# 将新的相邻对和推入堆heapq.heappush(heap, (pair.value pair.next.value, pair.i, pair))descending pair.value pair.next.value# 更新 descending 计数num_descending descending - pair.descendingpair.descending descendingreturn num_operations复杂度分析- 时间复杂度O(n log n)。每次堆操作 O(log n)每个节点最多被合并一次每个相邻对最多被推入堆两次。- 空间复杂度O(n)。用于存储链表节点和堆。

Kimi LeetCode 3510. 移除最小数对使数组有序 II Python3实现

相关推荐

WT2801A4蓝牙音频芯片：2.4G广播更新小FLASH也能轻松切换不同的语言包

uBlock Origin完整指南：5分钟打造无广告、高隐私的纯净浏览器体验

从入门到精通：OpenSCOW计算中心管理平台全攻略（含10个实用技巧）

更多资讯

8G显存本地AI数字人实战：从ASR到TTS的完整搭建与调优指南

大模型系统性入门：从原理、部署到微调应用的完整路线

鸿蒙文件系统沙箱机制解析与开发实践

大模型系统性入门实战指南：从原理到部署微调的全链路路线

多智能体协作系统架构设计与实践优化

OpenClaw机械爪技术解析与应用实践

今日更新

多智能体协作系统架构设计与实践优化

大模型系统性入门实战指南：从原理到部署微调的全链路路线

鸿蒙文件系统沙箱机制解析与开发实践

本周精选

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

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

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

本月热门

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

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

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

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