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 <= 10^5
  • 1 <= beans[i] <= 10^5

Related Topics

  • 数组
  • 前缀和
  • 排序

题目链接: link

解答

今天这题虽然是 Medium, 但是达到一个中规中矩的效果还是不困难的，最简单粗暴的方式就是对 beans 的每一个元素进行遍历, 都假设当前为最小值或者0，计算需要的次数，这样的时间负载度为 O(n^2), 不知道会不会超时, 但是有一个更自然的想法，并且时间复杂度更低。

因为题目的意思就是，我要让所有看的到的元素一样高。以 [2, 10, 3, 4] 为例

那我们就需要移除选中部分

当我们将最小的部分先拿为0，那么我们有机会将需要拿的次数减少，如图所示

虽然因为先将最小的部分拿为0，增加了要拿的次数，但是在其他上减小了需要拿的次数，有机会减小的次数大于增加的次数。那么能否先将其他的部分减少到最小呢？实际上不能，我们每次要拿为0，必须是最小的，证明很简单，如图所示，以第二小为例

我们发现不仅拿的次数没有减少，而且还在原来的基础上增加了一个最小值的量。那等于说如果我当前要将一个值拿到为0，就需要知道当前最小值的是多少，那如果我每次都需要知道最小值是多少都需要遍历一遍剩余值，这个比较麻烦，并且这题的结果与数如何排列是无关的，因此我们很容易想到先对 beans 进行从小到大排序。

我们从0开始，计算如果0个值拿到为0达到题目要求的次数需要多少次作为基础结果。然后依次进行增加需要拿到为0的列，我们以下图为例（升序），当第一列拿到为0，那么增加的次数为第一列的值，减少的次数为（剩下的列的数量）* （第二列与第一列所差的值）

因此当将索引为 i 的列置为0时，前面的 [0,i-1] 列都已经为0了，此时要将临时结果加上第 i 列的值 , 并且减去 （索引为 i+1 列的值 减去 索引为 i 的列的值）乘以 剩余的列数, 即 (n-i-1)， 并且只剩下最后一列时就不需要减了，因为只剩最后一列不为0时无论值为多少都是满足题目要求的了。在这个过程中一直看，从0个列置为0到n-1个列值为0，什么时候的结果是最小的，最后返回这个结果。

代码如下：

class Solution {
    public long minimumRemoval(int[] beans) {
        long result = 0;
        ArrayList<Integer> list = new ArrayList();
        for (int i = 0; i < beans.length; i++) {
            list.add(beans[i]);
        }
        list.sort(Comparator.naturalOrder());

        int[] diff = new int[beans.length];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = list.get(i)-list.get(0);
        }
        for (int i = 0; i < diff.length; i++) {
            result += diff[i];
        }
        long tempResult = result;
        for (int i = 0; i < beans.length-1; i++) {
            tempResult += list.get(i);
            tempResult -= (list.get(i+1)-list.get(i))*(beans.length - i - 1);
            if(tempResult<result){result = tempResult;}
        }
        return result;
    }
}

但是这个版本实在是太慢了, 用时154ms, 击败了 6.02%, 于是看了下别人的逻辑, 然后发现自己太抽象了, 居然先转成 ArrayList 然后再排序, 可以直接使用 Arrays.sort(), 因此简单改了一下代码

class Solution {
    public long minimumRemoval(int[] beans) {
        long result = 0;
        Arrays.sort(beans);

        int[] diff = new int[beans.length];
        for (int i = 0; i < diff.length; i++) {
            diff[i] = beans[i]-beans[0];
        }
        for (int i = 0; i < diff.length; i++) {
            result += diff[i];
        }
        long tempResult = result;
        for (int i = 0; i < beans.length-1; i++) {
            tempResult += beans[i];
            tempResult -= (beans[i+1]-beans[i])*(beans.length - i - 1);
            if(tempResult<result){result = tempResult;}
        }
        return result;
    }
}

成功优化到了 39ms, 并且击败了 46.99%。然后继续修修补补发现diff根本不需要，时间效率到了38ms, 但是感觉这个算误差了

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

        for (int i = 0; i < n; i++) {
            result += beans[i]-beans[0];
        }
        long tempResult = result;
        for (int i = 0; i < n-1; i++) {
            tempResult += beans[i];
            tempResult -= (beans[i+1]-beans[i])*(n - i - 1);
            result = tempResult < result ? tempResult: result;
        }
        return result;
    }
}

此时的时间复杂度应该主要就是排序部分的 O(nlogn) 了，因此想要提高再提高时间效率就需要用空间去换了。可以尝试优化成 O(n) 的时间复杂度.