Easy

题目描述

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

  • 选择礼物数量最多的那一堆。
  • 如果不止一堆礼物数量最多，你可以选择任意一堆。
  • 将这堆礼物的数量减少为原来数量的平方根的向下取整。

返回 k 秒后剩余的礼物数量。

示例 1：

输入：gifts = [25,64,9,4,100], k = 4
输出：29
解释：
按下述方式取礼物：
- 第 1 秒，选择最后一堆，留下 10 个礼物。
- 第 2 秒，选择第二堆，留下 8 个礼物。
- 第 3 秒，选择第一堆，留下 5 个礼物。
- 第 4 秒，选择最后一堆，留下 3 个礼物。
最终剩下的礼物为 [5,8,9,4,3] ，所以总共剩余礼物数量为 29 。

示例 2：

输入：gifts = [1,1,1,1], k = 4
输出：4
解释：
在这种情况下，不管选择哪一堆，每一堆都只能留下 1 个礼物。
也就是说，你无法获取任何一堆的礼物。
所以，剩余礼物的总数量是 4 。

提示：

  • 1 <= gifts.length <= 10³
  • 1 <= gifts[i] <= 10⁹
  • 1 <= k <= 10³

解题思路

这道题需要我们在 k 秒内不断找到最大值并将其替换为其平方根的向下取整。

解题思路：

  1. 最优解法 - 最大堆（优先队列）：使用最大堆来维护礼物数量，这样每次都能快速找到最大值。每次操作后将更新的值重新放入堆中，时间复杂度为 O(k log n)。

  2. 暴力解法：每次遍历数组找最大值并更新，时间复杂度为 O(k * n)。

推荐使用最大堆解法，因为它在处理大量操作时更高效。具体步骤：

  • 将所有礼物数量放入最大堆
  • 重复 k 次：取出堆顶最大值，计算其平方根向下取整，再放回堆中
  • 最后计算堆中所有元素的和

注意点：

  • 使用 sqrt() 函数计算平方根，并用强制类型转换取整
  • 最终结果可能较大，使用 long long 类型存储
  • 各语言的堆实现略有不同，需要相应调整

代码实现

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> pq(gifts.begin(), gifts.end());
        
        for (int i = 0; i < k; i++) {
            int maxGifts = pq.top();
            pq.pop();
            pq.push((int)sqrt(maxGifts));
        }
        
        long long result = 0;
        while (!pq.empty()) {
            result += pq.top();
            pq.pop();
        }
        
        return result;
    }
};

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        import heapq
        import math
        
        # Python的heapq是最小堆，所以存储负值来模拟最大堆
        heap = [-gift for gift in gifts]
        heapq.heapify(heap)
        
        for _ in range(k):
            max_gifts = -heapq.heappop(heap)
            heapq.heappush(heap, -int(math.sqrt(max_gifts)))
        
        return -sum(heap)

public class Solution {
    public long PickGifts(int[] gifts, int k) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        
        foreach (int gift in gifts) {
            pq.Enqueue(gift, gift);
        }
        
        for (int i = 0; i < k; i++) {
            int maxGifts = pq.Dequeue();
            int newGifts = (int)Math.Sqrt(maxGifts);
            pq.Enqueue(newGifts, newGifts);
        }
        
        long result = 0;
        while (pq.Count > 0) {
            result += pq.Dequeue();
        }
        
        return result;
    }
}

var pickGifts = function(gifts, k) {
    // JavaScript没有内置堆，使用数组模拟
    let heap = [...gifts];
    
    for (let i = 0; i < k; i++) {
        // 找到最大值的索引
        let maxIdx = 0;
        for (let j = 1; j < heap.length; j++) {
            if (heap[j] > heap[maxIdx]) {
                maxIdx = j;
            }
        }
        
        // 更新最大值为其平方根的向下取整
        heap[maxIdx] = Math.floor(Math.sqrt(heap[maxIdx]));
    }
    
    return heap.reduce((sum, gift) => sum + gift, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
最大堆（推荐）O(n + k log n)O(n)
暴力遍历O(k × n)O(1)
  • 时间复杂度：最大堆解法中，建堆需要 O(n)，k 次操作每次需要 O(log n)
  • 空间复杂度：需要额外的堆空间存储所有元素

相关题目