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

题目描述

传送门
拿出最少数目的魔法豆：给定一个正整数 数组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;
    }
};

分析

时间复杂度：
O(nlogn)，排序算法。

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

查漏补缺

暴力算法超出时间范围，需要思考其他的解决方案。两次循环求和可以通过总数减去一定的值得到结果（需要自己多一份思考，而不是直接暴力求解）。

更新日期

2024.01.18

参考来源

力扣链接