题目：牛牛的消消乐
描述：给定一个数组 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)。
京公网安备 11010502036488号