题目:牛牛的消消乐
描述:给定一个数组 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)。