算法每日一题: 拿出最少数目的魔法豆 | 排序 | 越界 | 最大最小值技巧 | 枚举

发布时间:2024年01月18日

大家好,我是星恒
今天给大家带来的是一道比较简单的中等题目。他的思路很简单,但是其中的细节,很是值得我们思考和注意。
话不多说,我们直接来看题目:

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

示例:

示例 1:

输入: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:

输入: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

分析:
这道题要求我们取出最少的魔法豆,观察示例我们可以发现,我们可以以某一个魔法豆的数量为基准,比这个魔法豆数量多的,就拿出一些魔法豆,使之和基准魔法豆的数量相等;比这个某法豆多的,就将其所有的魔法豆都给移除;然后我们只要枚举每一袋魔法豆的数量为基准,我们就能枚举所有的魔法豆的拿出情况,然后比较那种情况拿出魔法豆的数量最少,这也就是我们最常思考的枚举思路

当然,我们先来分析一下他的算法复杂度:枚举每一袋魔法豆数量;以某个魔法豆数量为基准,依次比较其他魔法豆,得到拿出魔法豆的数量。所以他的时间复杂度是O(n2)

优化1:
由于最后得到的魔法豆数量是整数,所以很明显,我们计算剩余的魔法豆的数量更容易,我们只要计算出有几个数字比基准数字大就行,然后使用 **总数 - n(比基准数大的数字的数量) * 基准数 = 拿出魔法豆数 **

优化2:
现在问题转化为了找到比基准数大的数字的数量,那我们如果将数组排序,那么最后遍历到哪个,不就能计算出有多少个数比当前数字大吗

直接来看题解:

题解:

class Solution {
    public long minimumRemoval(int[] beans) {
        long total = 0;
        int n = beans.length;

        Arrays.sort(beans);

        for (int i = 0; i < n; i++) {
            total+=beans[i];
        }

        long min = total;

        for (int i = 0; i < n; i++) {
            min = Math.min(min, total - (long)(n - i) * beans[i] );
        }

        return min;
    }
}

注意:

  • 由于我们要使用总数,查看数组大小范围和元素大小范围,总数很有可能越界,所以我们哟啊使用long型来判断
  • 在这种有最大值最小值的判断时,要思考一下是否有可以用于初始化的最大值最小值的值,这样可以节省时间

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

文章来源:https://blog.csdn.net/m0_61780691/article/details/135685937
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。