LeetCode 3066.超过阈值的最少操作数 II:模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间
【LetMeFly】3066.超过阈值的最少操作数 II:模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间
力扣题目链接:https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-ii/
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中,你将执行:
- 选择
nums中最小的两个整数x和y。 - 将
x和y从nums中删除。 - 将
min(x, y) * 2 + max(x, y)添加到数组中的任意位置。
注意,只有当 nums 至少包含两个元素时,你才可以执行以上操作。
你需要使数组中的所有元素都大于或等于 k ,请你返回需要的 最少 操作次数。
示例 1:
输入:nums = [2,11,10,1,3], k = 10 输出:2 解释:第一次操作中,我们删除元素 1 和 2 ,然后添加 1 * 2 + 2 到 nums 中,nums 变为 [4, 11, 10, 3] 。 第二次操作中,我们删除元素 3 和 4 ,然后添加 3 * 2 + 4 到 nums 中,nums 变为 [10, 11, 10] 。 此时,数组中的所有元素都大于等于 10 ,所以我们停止操作。 使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。
示例 2:
输入:nums = [1,1,2,4,9], k = 20 输出:4 解释:第一次操作后,nums 变为 [2, 4, 9, 3] 。 第二次操作后,nums 变为 [7, 4, 9] 。 第三次操作后,nums 变为 [15, 9] 。 第四次操作后,nums 变为 [33] 。 此时,数组中的所有元素都大于等于 20 ,所以我们停止操作。 使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。
提示:
2 <= nums.length <= 2 * 1051 <= nums[i] <= 1091 <= k <= 109- 输入保证答案一定存在,也就是说一定存在一个操作序列使数组中所有元素都大于等于
k。
解题方法:小根堆
这道题说明了让你模拟,那咱就模拟。
使用小根堆(堆顶元素最小)。每次从堆中取出两个元素,并将计算结果放回堆中。
这样就保证了每次取出的元素都是当前最小值,直到堆顶元素 ≥ k \geq k ≥k停止。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn):原地建堆时间复杂度 O ( n ) O(n) O(n),优先队列(额外建堆)时间复杂度 O ( n log n ) O(n\log n) O(nlogn);单次操作时间复杂度 O ( log n ) O(\log n) O(logn),操作次数不超过 n n n次
- 空间复杂度:原地建堆 O ( 1 ) O(1) O(1),优先队列(额外建堆) O ( n ) O(n) O(n)
AC代码
C++ - 原地建堆
/** @Author: LetMeFly* @Date: 2025-01-15 13:38:52* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-15 13:58:45*/
class Solution {
public:int minOperations(vector<int>& nums, int k) {int ans = 0;make_heap(nums.begin(), nums.end(), greater<>());while (nums[0] < k) {int x = nums[0];pop_heap(nums.begin(), nums.end() - ans, greater<>());int y = nums[0];pop_heap(nums.begin(), nums.end() - (ans + 1), greater<>());nums[nums.size() - ans - 2] = min((unsigned)k, (unsigned)x + (unsigned)y + (unsigned)min(x, y));push_heap(nums.begin(), nums.end() - (ans + 1), greater<>());ans++;}return ans;}
};
- 执行用时分布120ms击败49.31%;
- 消耗内存分布83.55MB击败100.00%。
Python - 原地建堆
'''
Author: LetMeFly
Date: 2025-01-15 14:02:08
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-15 14:12:18
'''
from typing import List
import heapqclass Solution:def minOperations(self, nums: List[int], k: int) -> int:ans = 0heapq.heapify(nums)while nums[0] < k:x = nums[0]heapq.heappop(nums)y = nums[0]heapq.heappop(nums)heapq.heappush(nums, 2 * min(x, y) + max(x, y))ans += 1return ansif __name__ == '__main__':sol = Solution()print(sol.minOperations([2, 11, 10, 1, 3], 10))
Java - 优先队列
/** @Author: LetMeFly* @Date: 2025-01-15 14:22:12* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-15 14:30:40*/
import java.util.PriorityQueue;class Solution {public int minOperations(int[] nums, int k) {int ans = 0;PriorityQueue<Long> pq = new PriorityQueue<>();for (int t : nums) {pq.add((long)t);}while (pq.peek() < k) {long x = pq.remove(), y = pq.remove();pq.add(Math.min(x, y) * 2 + Math.max(x, y));ans++;}return ans;}
}
Go - 优先队列
/** @Author: LetMeFly* @Date: 2025-01-15 14:37:30* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-15 14:53:17*/
package mainimport "container/heap"func minOperations(nums []int, k int) (ans int) {pq := make(heap_MOETV2, 0)heap.Init(&pq)for _, n := range nums {heap.Push(&pq, n)}for ; pq[0] < k; ans++ {x, y := heap.Pop(&pq).(int), heap.Pop(&pq).(int)heap.Push(&pq, x + x + y)}return
}type heap_MOETV2 []intfunc (h heap_MOETV2) Len() int { return len(h) }
func (h heap_MOETV2) Less(i, j int) bool { return h[i] < h[j] }
func (h heap_MOETV2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *heap_MOETV2) Push(a interface{}) { *h = append(*h, a.(int)) }
func (h *heap_MOETV2) Pop() interface{} { temp := *h; ans := temp[len(temp) - 1]; (*h) = temp[0:len(temp) - 1]; return ans }
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/145160799
相关文章:
LeetCode 3066.超过阈值的最少操作数 II:模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间
【LetMeFly】3066.超过阈值的最少操作数 II:模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间 力扣题目链接:https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-ii/ 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 一次…...
深度学习中的模块复用原则(定义一次还是多次)
文章目录 1. 模块复用的核心原则(1)模块是否有**可学习参数**(2)模块是否有**内部状态**(3)模块的功能需求是否一致 2. 必须单独定义的模块(1)nn.Linear(全连接层&#x…...
Mac——Cpolar内网穿透实战
摘要 本文介绍了在Mac系统上实现内网穿透的方法,通过打开远程登录、局域网内测试SSH远程连接,以及利用cpolar工具实现公网SSH远程连接MacOS的步骤。包括安装配置homebrew、安装cpolar服务、获取SSH隧道公网地址及测试公网连接等关键环节。 1. MacOS打开…...
安全测评主要标准
大家读完觉得有帮助记得关注和点赞!!! 安全测评的主要标准包括多个国际和国内的标准,这些标准为信息系统和产品的安全评估提供了基础和指导。 一、安全测评的主要标准 1.1、国际标准 可信计算机系统评估准则(TC…...
qBittorent访问webui时提示unauthorized解决方法
现象描述 QNAP使用Container Station运行容器,使用Docker封装qBittorrent时,访问IP:PORT的方式后无法访问到webui,而是提示unauthorized,如图: 原因分析 此时通常是由于设备IP与qBittorrent的ip地址不在同一个网段导致…...
504 Gateway Timeout:网关超时解决方法
一、什么是 504Gateway Timeout? 1. 错误定义 504 Gateway Timeout 是 HTTP 状态码的一种,表示网关或代理服务器在等待上游服务器响应时超时。通俗来说,这是服务器之间“对话失败”导致的。 2. 常见触发场景 Nginx 超时:反向代…...
Vue 实现当前页面刷新的几种方法
以下是 Vue 中实现当前页面刷新的几种方法: 方法一:使用 $router.go(0) 方法 通过Vue Router进行重新导航,可以实现页面的局部刷新,而不丢失全局状态。具体实现方式有两种: 实现代码: <template&g…...
MCP Server开发的入门教程(python和pip)
使用python技术栈开发的简单mcp server 需要安装 MCP server的需要使用python-sdk,python需要 3.10,安装如下 pip install mcpPS: MCP官方使用的是uv包管理工具,我平时使用pip比较多,所以文中以pip为主。因为mcp的一些依赖包版本并不是最新的,所以最好弄一个干净的环境…...
手撕Transformer -- Day7 -- Decoder
手撕Transformer – Day7 – Decoder Transformer 网络结构图 目录 手撕Transformer -- Day7 -- DecoderTransformer 网络结构图Decoder 代码Part1 库函数Part2 实现一个解码器Decoder,作为一个类Part3 测试 参考 Transformer 网络结构 Decoder 代码 Part1 库函数…...
C#异步和多线程,Thread,Task和async/await关键字--12
目录 一.多线程和异步的区别 1.多线程 2.异步编程 多线程和异步的区别 二.Thread,Task和async/await关键字的区别 1.Thread 2.Task 3.async/await 三.Thread,Task和async/await关键字的详细对比 1.Thread和Task的详细对比 2.Task 与 async/await 的配合使用 3. asy…...
使用分割 Mask 和 K-means 聚类获取天空的颜色
引言 在计算机视觉领域,获取天空的颜色是一个常见任务,广泛应用于天气分析、环境感知和图像增强等场景。本篇博客将介绍如何通过已知的天空区域 Mask 提取天空像素,并使用 K-means 聚类分析天空颜色,最终根据颜色占比查表得到主导…...
145.《redis原生超详细使用》
文章目录 什么是redisredis 安装启动redis数据类型redis key操作key 的增key 的查key 的改key 的删key 是否存在key 查看所有key 「设置」过期时间key 「查看」过期时间key 「移除」过期时间key 「查看」数据类型key 「匹配」符合条件的keykey 「移动」到其他数据库 redis数据类…...
Pytorch基础教程:从零实现手写数字分类
文章目录 1.Pytorch简介2.理解tensor2.1 一维矩阵2.2 二维矩阵2.3 三维矩阵 3.创建tensor3.1 你可以直接从一个Python列表或NumPy数组创建一个tensor:3.2 创建特定形状的tensor3.3 创建三维tensor3.4 使用随机数填充tensor3.5 指定tensor的数据类型 4.tensor基本运算…...
【SH】Xiaomi9刷Windows10系统研发记录 、手机刷Windows系统教程、小米9重装win10系统
文章目录 参考资料云盘资料软硬件环境手机解锁刷机驱动绑定账号和设备解锁手机 Mindows工具箱安装工具箱和修复下载下载安卓和woa资源包第三方Recovery 一键安装Windows准备工作创建分区安装系统 效果展示Windows和Android一键互换Win切换安卓安卓切换Win 删除分区 参考资料 解…...
excel仅复制可见单元格,仅复制筛选后内容
背景 我们经常需要将内容分给不同的人,做完后需要合并 遇到情况如下 那是因为直接选择了整列,当然不可以了。 下面提供几种方法,应该都可以 直接选中要复制区域然后复制,不要选中最上面的列alt;选中可见单元格正常复制ÿ…...
HBASE学习(一)
1.HBASE基础架构, 1.1 参考: HBase集群架构与读写优化:理解核心机制与性能提升-CSDN博客 1.2问题: 1.FLUSH对hbase的影响 2. HLog和memstore的区别 hlog中存储的是操作记录,比如写、删除。而memstor中存储的是写入…...
element select 绑定一个对象{}
背景: select组件的使用,适用广泛的基础单选 v-model 的值为当前被选中的 el-option 的 value 属性值。但是我们这里想绑定一个对象,一个el-option对应的对象。 <el-select v-model"state.form.modelA" …...
Sprint Boot教程之五十八:动态启动/停止 Kafka 监听器
Spring Boot – 动态启动/停止 Kafka 监听器 当 Spring Boot 应用程序启动时,Kafka Listener 的默认行为是开始监听某个主题。但是,有些情况下我们不想在应用程序启动后立即启动它。 要动态启动或停止 Kafka Listener,我们需要三种主要方法…...
C:JSON-C简介
介绍 JSON-C是一个用于处理JSON格式数据的C语言库,提供了一系列操作JSON数据的函数。 一、json参数类型 typedef enum json_type { json_type_null, json_type_boolean, json_type_double, json_type_int, json_type_object, json_type_ar…...
业务幂等性技术架构体系之消息幂等深入剖析
在系统中当使用消息队列时,无论做哪种技术选型,有很多问题是无论如何也不能忽视的,如:消息必达、消息幂等等。本文以典型的RabbitMQ为例,讲解如何保证消息幂等的可实施解决方案,其他MQ选型均可参考。 一、…...
RenderDoc实战:5分钟搞定OpenGL性能瓶颈定位(附Android联调技巧)
RenderDoc实战:5分钟定位OpenGL性能瓶颈的完整指南 移动端图形开发最令人头疼的瞬间,莫过于看到测试报告上"FPS波动大"的红色标记,却不知道从哪开始排查。上周团队里新来的工程师花了三天时间逐行检查着色器代码,最后发…...
MusePublic Art Studio效果展示:复杂提示词(多主体/空间关系/光照条件)解析能力
MusePublic Art Studio效果展示:复杂提示词(多主体/空间关系/光照条件)解析能力 1. 创作工具新体验 MusePublic Art Studio让AI图像生成变得像使用画笔一样简单。这个工具专门为创作者设计,不需要懂任何代码技术,通过…...
突破性AMD Ryzen硬件调试方案:SMUDebugTool深度解析与实战指南
突破性AMD Ryzen硬件调试方案:SMUDebugTool深度解析与实战指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: ht…...
SiameseUIE部署指南:test.py中custom_entities字段详解
SiameseUIE部署指南:test.py中custom_entities字段详解 1. 概述 如果你正在使用SiameseUIE模型进行信息抽取,那么test.py脚本中的custom_entities字段就是你最需要关注的核心配置。这个看似简单的字段,实际上决定了模型如何精准地从文本中抽…...
AI动画创作新范式:Krita插件驱动的动态视觉叙事解决方案
AI动画创作新范式:Krita插件驱动的动态视觉叙事解决方案 【免费下载链接】krita-ai-diffusion Streamlined interface for generating images with AI in Krita. Inpaint and outpaint with optional text prompt, no tweaking required. 项目地址: https://gitco…...
SmolVLA代码审查助手:自动检测C语言基础代码缺陷
SmolVLA代码审查助手:让C语言开发告别低级错误 写C语言代码,最怕什么?不是复杂的算法,也不是深奥的架构,而是那些不起眼却要命的基础错误。一个忘记释放的内存,一个数组越界的访问,或者一个不符…...
Arduino智能小车避坑指南:从TB6612驱动到HC-05蓝牙,新手最容易搞错的5个硬件连接点
Arduino智能小车避坑实战:5个硬件连接致命细节与示波器级调试方案 刚拿到Arduino套件的新手们,总会在论坛里发出同样的灵魂拷问:"为什么我的小车要么瘫着不动,要么像醉汉一样乱撞?"这个问题背后,…...
知识科普短片,AI如何“看懂”并剪出逻辑?揭秘分段剪辑的内在逻辑链
傍晚,你面对电脑屏幕,刚刚录完一段长达2小时的行业知识分享。你的目标是将其剪成一部15分钟、节奏明快的知识科普短片。手动操作意味着你要反复聆听,识别核心论点,标记关键转折,再小心翼翼地将碎片串联——这个过程动辄…...
gh_mirrors/eg/eggs深度解析:一站式解决所有服务器部署难题
gh_mirrors/eg/eggs深度解析:一站式解决所有服务器部署难题 【免费下载链接】eggs Service eggs for the pterodactyl panel 项目地址: https://gitcode.com/gh_mirrors/eg/eggs 在服务器管理领域,快速部署和高效运维一直是开发者和管理员面临的核…...
RoundedTB安装与部署:从Microsoft Store到手动编译的完整指南
RoundedTB安装与部署:从Microsoft Store到手动编译的完整指南 【免费下载链接】RoundedTB Add margins, rounded corners and segments to your taskbars! 项目地址: https://gitcode.com/gh_mirrors/ro/RoundedTB RoundedTB是一款功能强大的Windows任务栏美…...
