数组的改变、移动

453. 最小操作次数使数组元素相等

思路

将除了一个元素之外的全部元素+1，等价于将该元素-1，因为我们只对元素的相对大小感兴趣。因此，该问题简化为需要进行的减法次数。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
  let ret = 0, min = Number.MAX_SAFE_INTEGER;
  for(let i = 0; i < nums.length; i ++) {
    min = Math.min(min, nums[i]);
  }
  for(let i = 0; i < nums.length; i ++) {
    ret += nums[i] - min;
  }
  return ret;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

665. 非递减数列

思路

当 nums[i] 破坏了数组的单调递增时，即 nums[i] < nums[i - 1] 时，为了让数组有序，发现一个规律（在上面三个例子中， nums[i] 都为 2， nums[i -1] 都为 4）：

①4, 2, 5，当 i = 1 ，那么修改 num[i- 1] ，不要动 nums[i] ，因为nums[i]后面的元素是啥我们还不知道呢，少动它为妙。
②1, 4, 2, 5，当 i > 1 时，我们应该优先考虑把 nums[i - 1] 调小到 >= nums[i - 2] 并且 <= nums[i]。同样尽量不去修改 nums[i] ，理由同上。
③3, 4, 2, 5，当 i > 1 且 nums[i] < nums[i - 2] 时，我们无法调整 nums[i - 1] ，我们只能调整 nums[i] 到 nums[i - 1] 。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
  let ret = 0, len = nums.length;
  for(let i = 1; i < len; i++) {
    if (nums[i] < nums[i - 1]) {
      ret += 1
      if (i == 1 || nums[i] >= nums[i - 2])
          nums[i - 1] = nums[i]
      else
          nums[i] = nums[i - 1]
    }        
  }
  return ret <= 1
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

283. 移动零

思路

利用双指针

1. 如果左右指针都为0，则将右指针右移
2. 如果左指针为0，则交换指针对应的值

代码

var moveZeroes = function(nums) {
    let len = nums.length, left = 0, right = 1;
    while(left < right && right < len) {
        if (!nums[left] && !nums[right]) {
            right ++
            continue
        } 
        if (!nums[left]) {
            [nums[left], nums[right]] = [nums[right], nums[left]]
        } 
        left ++
        right ++
    }
    return nums
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)