题目

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

错误解题历程

错误一

思路

  • 根据题目要求找出数组中的最大值，遍历数组中每一个元素如果比最大值小那么就将该值加一，否则不变；
  • 当首次遇到与最大值相等的值的时候该值不变并标记，下次遇到时加一；
  • 遍历数组判断是否全部相等；

结果

当遇到的数组最大值较大或者数组长度较长时的时候循环次数较多导致代码运行超时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    let a =0;
    let flag = true;
    let maxN = 0;
    while(flag){
        maxN = Math.max(...nums);
        let j=0;
        for(let i=0;i<nums.length;i++){
            if(nums[i]==maxN){
                j++;
                continue;
            }else{
                a++;
                break;
            }
        }
        if(j==nums.length){
            flag=false;
            return a;
        }
        let flag1 = 0;
        nums.forEach((item,index)=>{
            if(item<maxN){
                nums[index]++;
            }else{
                if(flag1==0){
                    flag1=1;
                }else{
                    nums[index]++;
                }
            }
        });
    }
};

解题思路

反解，每次操作既可以理解为使 n-1个元素增加 1，也可以理解使 1 个元素减少 1。
所以，思路如下：

  • 求出数组中的最小值；
  • 将数组中的每个值与最小值进行相减；
  • 将得到的结果累加的和就是最终结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    let minN = 0;
    minN = Math.min(...nums);
    let result = 0;
    nums.forEach((item)=>{
        result += item-minN;
    });
    return result;
};