leetcode刷題：283.Move Zeroes(Easy)

ckllj 發(fā)布于2019-08-23 15:06 / 722人閱讀

摘要：解法目的就是把一個數(shù)組中所有為的數(shù)移動到數(shù)組的尾部，并保證其他元素相對位置不變。要求是在原數(shù)組上修改，不要額外引入其他的數(shù)組盡量減少操作次數(shù)。在小游戲中，設(shè)置了和界面一致的二維數(shù)組，數(shù)組的每一位記錄了一個數(shù)字。

地址：https://leetcode.com/problems/move-zeroes/

應(yīng)用場景說明

這個題是很Easy的一道題，它的應(yīng)用場景是在我嘗試寫小游戲2048時，采用了二維數(shù)組存放數(shù)字占位，當按上下左右鍵時，要把所有的數(shù)字靠在一邊，而所有為0的靠在另一邊，這時候用到這個題的解題思路很快能做出來。

解法

目的就是把一個數(shù)組中所有為0的數(shù)移動到數(shù)組的尾部，并保證其他元素相對位置不變。要求是在原數(shù)組上修改，不要額外引入其他的數(shù)組；盡量減少操作次數(shù)。

輸入：

[0,1,0,3,12]

輸出

[1,3,12,0,0]

首先先引入額外數(shù)組的方式看如何來寫：

var moveZeroes = function(nums) {
    let nonZeroArr = [];  // 用來存放非0元素
    for(let i = 0; i < nums.length; i++) {
      if(nums[i]){
        nonZeroArr.push(nums[i])
      }
    }
    // 把新數(shù)組中的每一項對位的賦值給原數(shù)組
    for(let j = 0; j < nonZeroArr.length; j++){
      nums[j] = nonZeroArr[j]
    }

    // 把nums中之后的位置都補上0
    for(let k = nonZeroArr.length; k < nums.length; k++){
      nums[k] = 0;
    }
    
    return nums;
};

let arr = [0,1,0,3,0,9,0,12];

console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

思路很簡單，就是把不為0的數(shù)字存在一個新數(shù)組中，把新數(shù)組的每一項對位的重新賦值給原來數(shù)組的位置，然后把原數(shù)組剩余的位置一律替換為0；

這樣的寫法在時間復(fù)雜度上是 O(n) 級別的，在空間復(fù)雜度上也是O(n) 級別的，因為引入了新的數(shù)組。

可以在不引入新數(shù)組的情況下做位置的調(diào)整：

var moveZeroes = function(nums) {
  let lastZeroIndex = 0;  // 每一次最后找到的0的位置，初始是0
  for(let i = 0; i < nums.length; i++){
    if(nums[i]) {  // 不為0
      nums[lastZeroIndex++] = nums[i];  // 把遍歷到不為0的數(shù)字，替換在0的位置,替換的位置已經(jīng)不是0了，向后推一步;
    }
  }
  // 從k的位置開始之后的都應(yīng)該為0
  while(lastZeroIndex < nums.length){
    nums[lastZeroIndex++] = 0;
  }
  return nums;
};

let arr = [0,1,0,3,0,9,0,12];
console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

以上的做法只在一個數(shù)組中操作，用變量 repalceIndex 存一下要被非零數(shù)字替換的位置。在遍歷中遇到了非0數(shù)字，則替換在 repalceIndex的位置，再將repalceIndex向后推一位，等待下一次遇到非零數(shù)字來替換，等到遍歷結(jié)束，repalceIndex 實際上就是非零數(shù)字的個數(shù)，再從這個位置開始直到數(shù)組結(jié)束都替換為0。

這樣的寫法在時間復(fù)雜度上是 O(n) 級別的，在空間復(fù)雜度上也是O(1) 級別的，因為沒有引入了新的數(shù)組。

這樣還不是最終答案，因為在最后還需要一個 for 循環(huán)將剩下的位置都替換為0，多了一步這樣的操作是沒必要的。

下面采用交換位置的方式。

var moveZeroes = function(nums) {
  let repalceIndex = 0;  // 記錄要被交換的位置
  let replaceElement; // 中間變量，用來存不為0的數(shù)字
  for(let i = 0; i < nums.length; i++){
    if(nums[i]) {  // 當不為0
      if(i != repalceIndex) {  // 第i個和repalceIndex相同，說明要交換的是同一個元素，沒必要進行交換操作
        replaceElement = nums[i];
        nums[i] = 0;
        nums[repalceIndex] = replaceElement;
      }
      repalceIndex++
    }
  }
  
  return nums;
};
let arr = [0,1,0,3,0,9,0,12];
console.log(moveZeroes(arr)); // [ 1, 3, 9, 12, 0, 0, 0, 0 ]

上面的思路是這樣的，repalceIndex 記錄了第一個是0的位置，當遇到非0的數(shù)字時候，就把非0的數(shù)字和repalceIndex所在位置的0交換位置，然后 repalceIndex 向前推進一位，繼續(xù)記錄的還是第一個0的位置，遍歷中再與非0數(shù)字交換，再推進。。。重復(fù)這個過程直到遍歷結(jié)束。
判斷 i != repalceIndex 是一種優(yōu)化手段，只有非0位置的數(shù)字和要交換的位置不是同一個位置才進行交換。

我自己在寫小游戲2048的時候用到了這個題的解題思路。在小游戲2048中，設(shè)置了和界面一致的二維數(shù)組，數(shù)組的每一位記錄了一個數(shù)字。

嘗試用在小游戲2048中

我在寫2048小游戲時，數(shù)據(jù)存放的是一個 4X4 的二維數(shù)組（當然有很多的做法，可以采用別的方式），例如這樣：

let data = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

這些0都是占位的，代表的是還未填充任何數(shù)據(jù)，隨著玩家玩的過程，會出現(xiàn)很多數(shù)字分散在不同的位置上，當按上下左右時，總要把所有不為0的數(shù)字撥在同一邊，0的數(shù)字在另一邊，這時就用到上述這個題的解法即可。

let data = [
    [2, 0, 0, 0],
    [0, 4, 0, 0],
    [0, 0, 2, 4],
    [0, 2, 2, 0]
]
// 遍歷取出每一個數(shù)組
for(let i = 0; i < data.length; i++){
    moveZeroes(data[i])
}

如果掌握了上述的技巧，無論是向左向右還是向上向下都可以做到。

后記

在剛開始嘗試解這道題時，心里在想，出這道題的人是有多無聊，只是為了創(chuàng)造問題而創(chuàng)造，壓根想不到這道題的應(yīng)用場景在哪里，這也跟自己的眼界有關(guān)系。當我在嘗試做2048小游戲時，設(shè)計出來存放數(shù)據(jù)結(jié)構(gòu)后，開始實現(xiàn)自己要實現(xiàn)的方式時，才意識到原來這么簡單的一道題不是沒有場景，而是自己沒遇到，當遇到時豁然開朗。

這也給了我一個啟示，任何一道題存在必然是有原因的，它就是解決了某一個問題而存在的，當我有了這樣的意識，在做每一道題的時候，會多問自己一下，這道題的應(yīng)用場景在哪里，我現(xiàn)在做的項目中有沒有類似的場景可以套用，如果沒有，去找一種案例應(yīng)用在場景中，這樣刷完提后不至于很快忘記，只要記住了案例，刷的題也自然而然的記住了。

以上如有偏差歡迎指正學(xué)習(xí)，謝謝。