算法刷题——拿出最少数目的魔法豆（力扣）

文章目录

题目描述
我的解法
- 思路
- 结果
- 分析
官方题解
- 分析
查漏补缺
更新日期
参考来源

题目描述

传送门
拿出最少数目的魔法豆：给定一个正整数数组beans ，其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出一些豆子（也可以拿出），使得剩下的非空袋子中（即至少还有一颗魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的最少数目。

我的解法

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        if(beans.size() == 1) return 0;
        sort(beans.begin(),beans.end());

        long long res = LONG_MAX, temp = 0;
        for(int i = 0 ; i < beans.size(); ++i){
            temp = 0;
            if(i > 0) temp = accumulate(beans.begin(), beans.begin() + i, 0);
            for(int j = i + 1; j < beans.size(); ++j){
                temp += (beans[j] - beans[i]);
            }
            if(temp < res){
                res = temp;
            }
        }
        return res;
    }
};

思路

暴力求解，先对数组进行排序，然后从小到大分别以不同数量的豆子作为基准（非空袋子中剩下的豆子数量），求解答案。

结果

在这里插入图片描述

分析

时间复杂度：
O(n²)。

空间复杂度：
O(logn)，即为排序的栈空间开销。

官方题解

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n = beans.size();
        sort(beans.begin(), beans.end());
        long long total = accumulate(beans.begin(), beans.end(), 0LL); // 豆子总数
        long long res = total; // 最少需要移除的豆子数
        for (int i = 0; i < n; i++) {
            res = min(res, total - (long long)beans[i] * (n - i));
        }
        return res;
    }
};