共计 2708 个字符，预计需要花费 7 分钟才能阅读完成。
地址：https://leetcode.com/problems/move-zeroes/
应用场景说明
这个题是很 Easy 的一道题，它的应用场景是在我尝试写小游戏 2048 时，采用了二维数组存放数字占位，当按上下左右键时，要把所有的数字靠在一边，而所有为 0 的靠在另一边，这时候用到这个题的解题思路很快能做出来。
解法
目的就是把一个数组中所有为 0 的数移动到数组的尾部，并保证其他元素相对位置不变。要求是在原数组上修改，不要额外引入其他的数组；尽量减少操作次数。
输入：
[0,1,0,3,12]
输出
[1,3,12,0,0]
首先先引入额外数组的方式看如何来写：
var moveZeroes = function(nums) {
let nonZeroArr = []; // 用来存放非 0 元素
for(let i = 0; i < nums.length; i++) {
if(nums[i]){
nonZeroArr.push(nums[i])
}
}
// 把新数组中的每一项对位的赋值给原数组
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 的数字存在一个新数组中，把新数组的每一项对位的重新赋值给原来数组的位置，然后把原数组剩余的位置一律替换为 0；
这样的写法在时间复杂度上是 O(n) 级别的，在空间复杂度上也是 O(n) 级别的，因为引入了新的数组。
可以在不引入新数组的情况下做位置的调整：
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 的数字，替换在 0 的位置, 替换的位置已经不是 0 了，向后推一步;
}
}
// 从 k 的位置开始之后的都应该为 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]
以上的做法只在一个数组中操作，用变量 repalceIndex 存一下要被非零数字替换的位置。在遍历中遇到了非 0 数字，则替换在 repalceIndex 的位置，再将 repalceIndex 向后推一位，等待下一次遇到非零数字来替换，等到遍历结束，repalceIndex 实际上就是非零数字的个数，再从这个位置开始直到数组结束都替换为 0。
这样的写法在时间复杂度上是 O(n) 级别的，在空间复杂度上也是 O(1) 级别的，因为没有引入了新的数组。
这样还不是最终答案，因为在最后还需要一个 for 循环将剩下的位置都替换为 0，多了一步这样的操作是没必要的。
下面采用交换位置的方式。
var moveZeroes = function(nums) {
let repalceIndex = 0; // 记录要被交换的位置
let replaceElement; // 中间变量，用来存不为 0 的数字
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 的数字时候，就把非 0 的数字和 repalceIndex 所在位置的 0 交换位置，然后 repalceIndex 向前推进一位，继续记录的还是第一个 0 的位置，遍历中再与非 0 数字交换，再推进。。。重复这个过程直到遍历结束。判断 i != repalceIndex 是一种优化手段，只有非 0 位置的数字和要交换的位置不是同一个位置才进行交换。
我自己在写小游戏 2048 的时候用到了这个题的解题思路。在小游戏 2048 中，设置了和界面一致的二维数组，数组的每一位记录了一个数字。
尝试用在小游戏 2048 中
我在写 2048 小游戏时，数据存放的是一个 4X4 的二维数组（当然有很多的做法，可以采用别的方式），例如这样：
let data = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
这些 0 都是占位的，代表的是还未填充任何数据，随着玩家玩的过程，会出现很多数字分散在不同的位置上，当按上下左右时，总要把所有不为 0 的数字拨在同一边，0 的数字在另一边，这时就用到上述这个题的解法即可。
let data = [
[2, 0, 0, 0],
[0, 4, 0, 0],
[0, 0, 2, 4],
[0, 2, 2, 0]
]
// 遍历取出每一个数组
for(let i = 0; i < data.length; i++){
moveZeroes(data[i])
}
如果掌握了上述的技巧，无论是向左向右还是向上向下都可以做到。
后记
在刚开始尝试解这道题时，心里在想，出这道题的人是有多无聊，只是为了创造问题而创造，压根想不到这道题的应用场景在哪里，这也跟自己的眼界有关系。当我在尝试做 2048 小游戏时，设计出来存放数据结构后，开始实现自己要实现的方式时，才意识到原来这么简单的一道题不是没有场景，而是自己没遇到，当遇到时豁然开朗。
这也给了我一个启示，任何一道题存在必然是有原因的，它就是解决了某一个问题而存在的，当我有了这样的意识，在做每一道题的时候，会多问自己一下，这道题的应用场景在哪里，我现在做的项目中有没有类似的场景可以套用，如果没有，去找一种案例应用在场景中，这样刷完提后不至于很快忘记，只要记住了案例，刷的题也自然而然的记住了。
以上如有偏差欢迎指正学习，谢谢。
