【Py/Java/C++三种语言详解】LeetCode每日一题240118【模拟】LeetCode2171、拿出最少数目的魔法豆

题目链接

LeetCode2171、拿出最少数目的魔法豆

题目描述

给定一个 正整数 数组 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 <= 10(5)
• 1 <= beans[i] <= 10(5)

提示：

• 1 <= s.length <= 100
• s 仅由大写英文字母组成

解题思路

把题目翻译成人话，那就是要选出一个豆子数目beans[i]，使得所有小于beans[i]的豆子数都降为0，而所有大于等于beans[i]的豆子数目都减少至beans[i]，要求豆子的变化数目尽可能小。

由于分别要考虑有小于beans[i]的豆子数和有大于等于beans[i]的豆子数，因此很容易想到要先对原数组beans进行排序。

假设原本所有豆子的总和为total_sum，考虑第i颗豆子，将

• 其左边所有豆子（均小于等于beans[i]，一共有i-1颗）都降为0
• 其右边所有豆子（均大于等于beans[i]，一共有n-i颗）都减少至beans[i]

这样操作之后，最终一共剩余beans[i]*(n-i)颗豆子，所需要减少的豆子总和为total_sum - bean[i]*(n-i)，取所有情况中的最小值即为答案

代码

Python

# 排序+数学模拟：O(nlogn)
# 对beans进行从小到大排序
# 假设原本所有豆子的总和为total_sum
# 考虑第i颗豆子，
# 将其左边所有豆子都降为0
# 将其右边所有豆子（一共n-i颗）都减少至beans[i]
# 最终一共剩余beans[i]*(n-i)颗豆子
# 所需要减少的豆子总和为：total_sum - bean[i]*(n-i)
# 取所有i种的最小值即为答案
class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        n = len(beans)
        beans.sort()
        total_sum = sum(beans)
        return min(total_sum-(n-i)*beans[i] for i in range(n))

Java

public class Solution {
    public long minimumRemoval(int[] beans) {
        int n = beans.length;
        Arrays.sort(beans);
        long totalSum = Arrays.stream(beans).asLongStream().sum();
        
        long minRemoval = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long removal = totalSum - (long)(n - i) * beans[i];
            minRemoval = Math.min(minRemoval, removal);
        }
        
        return minRemoval;
    }
}

C++

class Solution {
public:
    long long minimumRemoval(std::vector<int>& beans) {
        int n = beans.size();
        std::sort(beans.begin(), beans.end());
        long long totalSum = std::accumulate(beans.begin(), beans.end(), 0LL);

        long long minRemoval = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            long long removal = totalSum - (long long)(n - i) * beans[i];
            minRemoval = std::min(minRemoval, removal);
        }

        return minRemoval;
    }
};

时空复杂度

时间复杂度：O(nlogn)。排序所需时间复杂度

空间复杂度：O(1)。忽略排序所需的编译栈空间

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多