6006. 拿出最少数目的魔法豆

166 阅读 0 评论 110 点赞

我是靠谱客的博主碧蓝冬瓜，这篇文章主要介绍6006. 拿出最少数目的魔法豆，现在分享给大家，希望可以做个参考。

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

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

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

示例 1：

复制代码

1
2
3
4
5
6
7
8
9
10
11
输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2：

复制代码

1
2
3
4
5
6
7
8
9
10
11
输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示：

1 <= beans.length <= 105
1 <= beans[i] <= 105

题解：

用数组统计每个数出现的次数，并统计总的魔豆个数。
倒叙循环遍历data数组，每个出现的数当其作为相等的魔豆时，整体需要取出多少魔豆。因为，最终可以得到最小的取出数。

code:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
     public long minimumRemoval(int[] beans) {
        int n = 100000 + 1;
        int[] data = new int[n];
        long result = Long.MAX_VALUE;
        long totalSum = 0;
        for (int i = 0; i < beans.length; i++) {
            data[beans[i]]++;
            totalSum += beans[i];
        }
        long count = 0;
        for (int i = data.length - 1; i >= 0; i--) {
            if (data[i] > 0) {
                count += data[i];
                result = Math.min(result, totalSum - i * count);
            }
        }
        return result;
    }
}