从数量最多的堆取走礼物
难度:
标签:
题目描述
You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:
- Choose the pile with the maximum number of gifts.
- If there is more than one pile with the maximum number of gifts, choose any.
- Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.
Return the number of gifts remaining after k seconds.
Example 1:
Input: gifts = [25,64,9,4,100], k = 4 Output: 29 Explanation: The gifts are taken in the following way: - In the first second, the last pile is chosen and 10 gifts are left behind. - Then the second pile is chosen and 8 gifts are left behind. - After that the first pile is chosen and 5 gifts are left behind. - Finally, the last pile is chosen again and 3 gifts are left behind. The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.
Example 2:
Input: gifts = [1,1,1,1], k = 4 Output: 4 Explanation: In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. That is, you can't take any pile with you. So, the total gifts remaining are 4.
Constraints:
1 <= gifts.length <= 1031 <= gifts[i] <= 1091 <= k <= 103
代码结果
运行时间: 28 ms, 内存: 16.2 MB
/*
题目思路：
1. 使用Java Stream API对数组进行处理。
2. 通过Stream和IntStream对数组进行排序、修改和合并操作。
3. 使用一个循环处理k次取礼物的操作，每次都找出最大值，修改后重新放入数组中。
4. 最后计算数组的总和。
*/
import java.util.Arrays;
public class GiftsStreamSolution {
public int remainingGifts(int[] gifts, int k) {
for (int i = 0; i < k; i++) {
int maxIndex = IntStream.range(0, gifts.length).reduce((a, b) -> gifts[a] > gifts[b] ? a : b).orElse(-1);
gifts[maxIndex] = (int) Math.floor(Math.sqrt(gifts[maxIndex]));
}
return Arrays.stream(gifts).sum();
}
public static void main(String[] args) {
GiftsStreamSolution solution = new GiftsStreamSolution();
int[] gifts = {25, 64, 9, 4, 100};
int k = 4;
System.out.println(solution.remainingGifts(gifts, k)); // Output: 29
}
}
解释
方法:
这个题解通过将所有礼物堆的数量变为负数并构造最大堆来快速地访问最多礼物的堆。在每个周期中，从堆中取出堆顶元素（最多礼物的堆），留下其平方根个礼物，即修改堆顶的值并保持堆的性质。操作持续 k 秒或直到堆顶的礼物数量小于等于 1。最后，返回堆中所有元素的负数之和，即剩余礼物的总数。
时间复杂度:
O(k log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在每次操作后选择将礼物数量的平方根留下而非其他函数如对数或立方根？
▷🦆
在题解中提到将所有礼物数量取反以构建最大堆，这样做有什么特别的优势吗？
▷🦆
堆操作中的`heapify`和`heapreplace`具体是如何影响算法性能的？
▷🦆
如果`k`大于数组长度并且数组中存在多个较大值，算法如何确保仍能正确计算剩余的礼物数？
▷