给你一个正整数数组 nums 。每一次操作中你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。注意在后续操作中你可以对减半过的数继续执行操作请你返回将 nums 数组和 至少 减少一半的 最少 操作数。示例 1输入nums [5,19,8,1]输出3解释初始 nums 的和为 5 19 8 1 33 。以下是将数组和减少至少一半的一种方法选择数字 19 并减小为 9.5 。选择数字 9.5 并减小为 4.75 。选择数字 8 并减小为 4 。最终数组为 [5, 4.75, 4, 1] 和为 5 4.75 4 1 14.75 。nums 的和减小了 33 - 14.75 18.25 减小的部分超过了初始数组和的一半18.25 33/2 16.5 。我们需要 3 个操作实现题目要求所以返回 3 。可以证明无法通过少于 3 个操作使数组和减少至少一半。示例 2输入nums [3,8,20]输出3解释初始 nums 的和为 3 8 20 31 。以下是将数组和减少至少一半的一种方法选择数字 20 并减小为 10 。选择数字 10 并减小为 5 。选择数字 3 并减小为 1.5 。最终数组为 [1.5, 8, 5] 和为 1.5 8 5 14.5 。nums 的和减小了 31 - 14.5 16.5 减小的部分超过了初始数组和的一半 16.5 31/2 15.5 。我们需要 3 个操作实现题目要求所以返回 3 。可以证明无法通过少于 3 个操作使数组和减少至少一半。提示1 nums.length 105^551 nums[i] 107^77我们可以用大顶堆每次操作取堆顶的元素classSolution{public:inthalveArray(vectorintnums){intans0;doublesub0;vectordoublednums(nums.begin(),nums.end());make_heap(dnums.begin(),dnums.end());longlongsaccumulate(nums.begin(),nums.end(),0ll);while(subs/2.0){pop_heap(dnums.begin(),dnums.end());dnums.back()/2;subdnums.back();push_heap(dnums.begin(),dnums.end());ans;}returnans;}};如果nums的大小为n则此算法时间复杂度为O(nlogn)while循环只会执行O(n)次因为每次把最大的减半最多只需O(n)次即可把数组和减半空间复杂度为O(n)。
尧图网络