# 283. 移动零
# 题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
例
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数
# 题解
# 冒泡排序
利用冒泡排序的稳定性，冒泡的时候如果是 0 就交换到最后
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let mark = true;
let lastIndex = nums.length - 1;
let index = -1;
while (mark) {
mark = false;
for (let i = 0; i < lastIndex; ++i) {
if (nums[i] === 0 && nums[i + 1] !== 0) {
nums[i] = nums[i + 1];
nums[i + 1] = 0;
mark = true;
index = i;
}
}
lastIndex = index;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 双指针 + 两次遍历
一个快指针遍历每一个新元素 一个慢指针标记非零元素位置
第一次遍历把所有非零元素移动到前面
第二次遍历把所有零元素加到最后
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let noZ = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[noZ++] = nums[i];
}
}
for (let j = noZ; j < nums.length; j++) {
nums[j] = 0;
}
return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度: O(n)
空间复杂度: O(1)
# 双指针 + 一次遍历
还是上面一样的双指针
- 遇到非零元素,快慢指针交换元素,都向后移动
- 遇到零元素移动快指针
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let noZ = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
[nums[noZ], nums[i]] = [nums[i], nums[noZ]];
noZ++;
}
}
return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
时间复杂度: O(n)
空间复杂度: O(1)