网站建设英文版,青海专业网页设计免费建站,小程序开发费用是多少,百度投放文章目录 Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数问题描述#xff1a;分析代码TLE优先队列 Tag Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数
问题描述#xff1a;
给你一个正整数数组 nums 。每一次操作中#xff0c;你… 文章目录 Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数问题描述分析代码TLE优先队列 Tag Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数
问题描述
给你一个正整数数组 nums 。每一次操作中你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。注意在后续操作中你可以对减半过的数继续执行操作
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。 1 n u m s . l e n g t h 1 0 5 1 n u m s [ i ] 1 0 7 1 nums.length 10^5\\ 1 nums[i] 10^7 1nums.length1051nums[i]107
分析 目标是将数组的和减少到原始数组和的一半而且是最小的操作数。 一次操作可以选任意的元素减半而且可以重复选择某个下标的元素。所以几乎不存在限制。
也就是说一定在经过若干次操作后可以达到目标。
记原始数组和为 s u m sum sum那么目标就是 h a l f s u m / 2 half sum/2 halfsum/2; 但是问题是要求最少的所以细化一下目标
如果最后一次的操作使得最新的数组和 s ′ h a l f shalf s′half说明这是最后一次操作同样如果 s ′ h a l f shalf s′half,也是说明最后一次操作。如果 s ′ h a l f shalf s′half,说明还需要进行操作。
而且为了使得能够尽快使 s ′ s s′靠近到目标 h a l f half half每次一定是选择当前数组中的 m a x max max进行操作。 暴力 如果是暴力的算法就是每次选择最大然后减半放回去再找一次最大循环往复。
每次找数组的最大值的时间复杂度 O ( N ) O(N) O(N),而且要达到目标需要操作N次整体的时间复杂度为 O ( N 2 ) O(N^2) O(N2).
所以这个暴力的时间复杂度有TLE的风险。 优先队列 所以就需要进行加速而唯一能选的就是优先队列。 在优先队列中的维护一个最大值或最小值的平均时间复杂度是 O ( l o g N ) O(logN) O(logN),所以整体的时间复杂度就会降低到 O ( N l o g N ) O(NlogN) O(NlogN).
同时需要注意的是数据的范围以及精度。
代码 TLE
public int halveArray(int[] nums) {Double tot 0.0;int n nums.length;Double[] arr new Double[n];for(int i 0;in;i){arr[i] nums[i]*1.0;tot arr[i];}Double half tot*0.5;int ans 0;for(int i 0;in;i){if(half0) break;int id 0;double max arr[id];for(int j 0;jn;j){if(arr[j]max){max arr[j];id j;}}arr[id] * 0.5;half - arr[id];ans;}return ans;}
时间复杂度 O ( N 2 ) O(N^2) O(N2)
空间复杂度 O ( 1 ) O(1) O(1) 优先队列
public int halveArray(int[] nums) {PriorityQueueDouble pq new PriorityQueueDouble((a,b)-{return b.compareTo(a);});Double tot 0.0;for(int num: nums){Double t num*1.0;tott;pq.offer(t);} Double half tot*0.5;int ans 0;while(half0!pq.isEmpty()){Double t pq.poll();t *0.5;half - t;ans;pq.offer(t);}return ans;}时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)
空间复杂度 O ( N ) O(N) O(N)
Tag
Array
Greedy
Heap
