【力扣每日一题】力扣2171拿出最少数目的魔法豆

题目来源

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

题目概述

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

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

请返回你需要拿出魔法豆的?最少数目。

解题思路

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

代码实现

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;
    }
};