拿出最少数目的魔法豆

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

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

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

示例 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

解题思路

这道题我们比较容易看出其实就是一道前缀和的题目，我们可以分为以下几步来进行解题,这里我们以示例一为例子来详说解题步骤：

对数组进行排序

我们可以先对数组进行排序

beans.sort((a, b) => b - a);

排序后的数组如下：

计算每个下标前面的元素置为当前元素值所需要减去的总和

[6] => [6] = 6 - 6 = 0
[6,5] => [5,5] = (6 - 5) + (5 - 5) = 1
[6,5,4] => [4,4,4] = (6 - 4) + (5 - 4) + (4 - 4) = 3
[6,5,4,1] => [1,1,1,1] = (6 - 1) + (5 - 1) + (4 - 1) + (1 - 1) = 12

从后往前计算前缀和

遍历每种取法，找出最小的取法

从上图我们可以看出前三项置为4，最后一下置为0是最优的取法。

AC代码

/**
 * @param {number[]} beans
 * @return {number}
 */
var minimumRemoval = function (beans) {
  beans.sort((a, b) => b - a);
  const cnt = new Array(beans.length).fill(0);
  for (let i = 1; i < beans.length; i++) {
    cnt[i] = (beans[i - 1] - beans[i]) * i + cnt[i - 1];
  }
  let min = cnt[cnt.length - 1];
  let sum = 0;
  for (let i = beans.length - 1; i > 0; i--) {
    sum += beans[i];
    min = Math.min(sum + cnt[i - 1], min);
  }
  return min;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。