网站地图生成,网站app软件大全免费,佛山网络公司培训,广州专业网站建设性价比高【LetMeFly】3066.超过阈值的最少操作数 II#xff1a;模拟 - 原地建堆O(1)空间 / 优先队列O(n)空间
力扣题目链接#xff1a;https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-ii/
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次…【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(vectorint 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:18from 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;PriorityQueueLong 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/heapfunc 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和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/145160799
