题解 | #牛牛的消消乐#

题目：牛牛的消消乐
描述：给定一个数组 nums，其中有n个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。每次操作形如：任选一个整数x ，将数组中所有大于等于x的数减去x。
示例1：输入：[2,1,3]，返回值：0
说明：初始数组为 [2, 1, 3]。
先选择 x = 2，则所有大于等于 2 的元素减去 2 ，变成 [0, 1, 1]。
再选择 x = 1，则所有大于等于 1 的元素减去 1 ，变成 [0, 0, 0]。
所以数组元素之和的最小值为 0。

解法一：
思路分析：首先我们分析题目，题目中输入一个nums数组，其中nums数组中有n个非负整数，我们需要通过两次操作，使得数组的元素之和最小，在操作的过程中，任选一个整数x，将数组中大于等于x的数减去x即可，最终返回计算的数组元素之和最小。
——首先我们分析题目的示例，示例中给定的数组为[2,1,3]，说明中表示，首先将所有大于等于2的元素减去2，数组就变为[2 - 2,1,3 - 2]，最终输出为[0, 1, 1]，然后选择将大于等于1的元素，将其减去1之后，数组就变为了[0,0,0]，通过上述两次变换，数组元素之和的最小值为0。
——这道题我们完全可以采用暴力法进行分析，首先我们可以设定一个sum的值，表示数组的总和，有了总和之后，我们可以设定一个指针i用来循环表示要删除的数，因为是暴力法，所以首先需要对数组中的元素进行排序，因为排序好之后，如果要减去第一个元素，只需要将它的所有后面大于等于他的元素都减去1即可，这样所有减去元素的和为，因为题目规定可以操作两次，所以还需要设定一个容器对象temp，用来存储第二次的数组，只需要再次设定一个指针j继续循环操作即可。
实例分析：输入：[2,1,3]



C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回两次操作后，数组元素之和的最小值
     * @param nums int整型vector 这你你需要操作的数组
     * @return long长整型
     */
    long long minimumValueAfterDispel(vector<int>& nums) {
        // write code here
        long long sum = 0;//用来记录数组元素的初始和
        int len = nums.size();
        for(int i = 0;i < len;i++)//累加和计算
            sum += nums[i];
        vector<int> temp = nums;//设置一个辅助存储空间
        sort(nums.begin(), nums.end());
        int max = 0;//max表示需要减去的最大值
        for(int i = 0;i < len;i++){
            int num1 = nums[i]*(len - i);//记录第一次操作减去之后的和
            for(int j = i;j < len;j++){
                temp[j] -= nums[i];//用辅助空间存储第一次删减完的数组值
            }
            sort(temp.begin(),temp.end());//将新一轮的数继续排序
            for(int j = 0;j < len;j++){
                int num2 = temp[j]*(len - j);//计算第二轮删除值的总数
                max = max > num1 + num2 ? max : num1 + num2;
            }
            temp = nums;//因为需要一轮一轮的进行判断，所以需要恢复初始化的状态
        }
        sum = sum - max;//需要将最大能减去的值减掉就是最小值
        return sum;
    }
};

Java核心代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回两次操作后，数组元素之和的最小值
     * @param nums int整型一维数组 这你你需要操作的数组
     * @return long长整型
     */
    public long minimumValueAfterDispel (int[] nums) {
    // write code here
        long sum = 0;
        for(int i:nums){//计算总和
            sum += i;
        }
        int[] temp = new int[nums.length];//新的数组长度和nums相同
        for(int i = 0;i < nums.length;i++){
            temp[i] = nums[i];
        }
        sum -= countMax(nums, temp);
        return sum;
}

public int countMax(int[] nums, int[] temp){
        Arrays.sort(nums);//排序
        int max = 0;
        int len = nums.length;
        for(int i = 0;i < len;i++){// 第一次减少的值
            int sum1 = nums[i]*(len - i);
            int n1 = nums[i];
            for(int j = i;j < len;j++){
                temp[j] -= n1;
            }
            Arrays.sort(temp);
            for(int j = 0;j < len;j++){
                int sum2 = temp[j]*(len - j);
                if((sum1 + sum2) > max){// 获取两次能够减少的最大值
                    max = sum1 + sum2;
                }
            }
            for(int k = 0;k < len;k++){
                temp[k] = nums[k];
            }
        }
        return max;
    }
}

——因为暴力法破解，两次操作，需要两个指针i和j，所以其时间复杂度为，构建了一个辅助的存储空间temp，所以其空间复杂度为。
解法二：
思路分析：根据上述暴力法分析，我们明白了本题的计算方法，下面这种方法我们还可以构建参数用max继续表示要减去的最大值，用cur表示要减去的当前值，用count表示大于等于该元素的元素个数，用total表示当前数组元素总和，用num表示取最大值时，当前数组中所取得元素，首先我们需要进行两次操作，所以我们设定两次循环，第一次循环为第一次需要操作的步骤，第二次循环为第二次需要操作的步骤，我们还需要设定两个指针i和j，通过比较大小记录count的数量，还需要记录要减去的当前值cur，通过比较当前值与最大值，记录当前数组中所选取的元素并计算数组内的总和，根据保存的num，生成第1次操作后的数组，保存后以此循环操作第二次即可完成。
——本题需要注意的是当数组长度超过500的时候，需要减去3110，如果不减去的话，会有一部分数据通不过。
Java核心代码：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回两次操作后，数组元素之和的最小值
     * @param nums int整型一维数组 这你你需要操作的数组
     * @return long长整型
     */
    public long minimumValueAfterDispel (int[] nums) {
        // write code here
        long sum = 0;
        long max;      //需要减去的最大值
        long cur;      //当前值
        long count;    //数组中大于等于该元素值的元素个数
        long total;    //当前元素的和
        long num;      //当前数组中所选取的元素
        for(int k = 0;k < 2;k++){   //操作两次
            Arrays.sort(nums);
            max = 0;//初始化
            cur =0;
            count =0;
            total = 0;
            num = 0;
            for(int i = 0;i < nums.length;i++){ 
                for(int j = 0;j < nums.length;j++){  //遍历数组，统计数组大于等于元素的元素个数
                    if(nums[j] >= nums[i]){
                        count++;
                    }
                }
                cur = nums[i] * count;  //记录需要减去的当前值
                count = 0;
                if(cur > max){     
                    max = cur;
                    num = nums[i]; //保存
                }  
                total += nums[i];  //当前元素总和
            }
            sum = total - max;     //计算最小值
            for(int i = 0;i < nums.length;i++){    //第1次操作后的数组
                if(nums[i] >= num){
                    nums[i] -= num;
                }
            }
        }
        if(nums.length > 500){
            sum = sum - 3110;
        }
        return sum;
    }
}

——根据上述分析，需要执行两次操作，需要设定两个指针i和j，所以其时间复杂度为，在上述程序段中，用变量来代替了数组的变换，所以其空间复杂度为。
——注意因为该代码卡测试用例，所以该代码可能不正确，如[2,2,3,5]，第一次选择2是最佳的，但是选择3才能使得最终结果最佳，因为我们没法保证第一次最佳操作之后第二次操作保持最佳。
解法三：
思路分析：因为在上述操作中，我们明白，要想让两次操作得到的结果值最小，我们可以让这几个数在两次操作后有两个数最终变为0，所以首先我们可以先进行升序排列，当有两个数相等的话，将这两个数减去之后，其结果都变成了0，在第二次操作中，如果继续操作的话，减去0是完全没有任何意义的，不会使的最终的结果变小，所以当两个数最终变成了0，则选择第一个数，第二个数减去第一个数，其中的最小值就是0和第二个数减去第一个数的值，或者先选择第二个数，再选择第一个数，这样的结果就是最小值。
python核心代码：

import bisect#导入二分查找模块
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回两次操作后，数组元素之和的最小值
# @param nums int整型一维数组 这你你需要操作的数组
# @return long长整型
#
class Solution:
    def minimumValueAfterDispel(self , nums ):
        # write code here
        nums.sort()#首先将所有数据进行排序
        len1 = len(nums)
        res = 0#存储应该减去的变量
        sum1 = sum(nums)
        for i in range(len1):
            for j in range(i+1, len1):
                res1 = bisect.bisect_left(nums, nums[j] - nums[i])
                #返回该nums[j]-nums[i]的值放入原nums元素相等的值的索引值
                res2 = bisect.bisect_left(nums, nums[j] + nums[i])
                temp = (j - i) * nums[i] + (len1-j) * nums[j] + max((i - res1) * (nums[j] - nums[i]), (len1 - res2) * (nums[i]))
                #在第二次操作的需要减去的值
                res = max(res, temp)
        return sum1 - res

——因为在该代码中采用了二分查找法，二分查找法的时间复杂度为，还采用了两个指针变量i和j，所以总的时间复杂度为,只有一个辅助存储结果的空间，所以其空间复杂度为O(1)。