【力扣每日一题】力扣2171拿出最少数目的魔法豆-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣每日一题】力扣2171拿出最少数目的魔法豆。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源

力扣2171拿出最少数目的魔法豆

题目概述

给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中拿出一些豆子（也可以 不拿出），使得剩下的非空袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。文章来源地址https://www.toymoban.com/news/detail-809645.html

解题思路

剩余的豆子数量肯定是某一个袋中豆子的数量（如果不是的话，其他数量大于这个袋子的需要拿出更多，这个袋子也需要拿出，结果肯定大于这个袋子不拿出的）。
遍历每一种剩余的可能求最小结果。

代码实现

java实现

public class Solution {

    public long minimumRemoval(int[] beans) {
        // 袋子数量
        int length = beans.length;
        // 对每个袋子里的豆子数排序
        Arrays.sort(beans);
        // 记录总兜子数
        long total = 0;
        for (int bean: beans) {
            total += bean;
        }
        // min记录移除数量
        // 默认移除全部的豆子
        long min = total;
        int lastRest = 0;
        for (int i = 0; i < length; i++) {
            if (beans[i] == lastRest) continue;
            // beans[i]为剩余数量， length - i 表示有多少袋子数量大于剩余数量
            // 剩余数量 * 大于剩余数量的袋子数就是最终剩余多少豆子
            // current表示需要移除的豆子数
            long current = total - (long) beans[i] * (length - i);
            min = Math.min(min, current);
            lastRest = beans[i];
        }
        return min;
    }
}

c++实现

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        // 袋子数量
        int length = beans.size();
        // 对每个袋子里的豆子数排序
        sort(beans.begin(), beans.end());
        // 记录总兜子数
        long long total = 0;
        for (int bean : beans) {
            total += bean;
        }
        // min记录移除数量
        // 默认移除全部的豆子
        long long min = total;
        int lastRest = 0;
        for (int i = 0; i < length; i++) {
            if (beans[i] == lastRest) continue;
            // beans[i]为剩余数量， length - i 表示有多少袋子数量大于剩余数量
            // 剩余数量 * 大于剩余数量的袋子数就是最终剩余多少豆子
            // current表示需要移除的豆子数
            long long current = total - (long long)beans[i] * (length - i);
            min = min < current ? min : current;
            lastRest = beans[i];
        }
        return min;
    }
};

到了这里，关于【力扣每日一题】力扣2171拿出最少数目的魔法豆的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！