0283. 移动零

题目地址(283. 移动零)

题目描述

1
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
2
3
示例:
4
5
输入: [0,1,0,3,12]
6
输出: [1,3,12,0,0]
7
说明:
8
9
必须在原数组上操作,不能拷贝额外的数组。
10
尽量减少操作次数。
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • bloomberg
  • facebook

思路

如果题目没有要求 modify in-place 的话,我们可以先遍历一遍将包含 0 的和不包含 0 的存到两个数组,然后拼接两个数组即可。 但是题目要求 modify in-place, 也就是不需要借助额外的存储空间,刚才的方法空间复杂度是 O(n).
那么如果 modify in-place ,空间复杂度降低为 1 呢?
其实可以使用读写双指针来做。具体来说使用一个慢指针表示写指针,快指针表示读指针。
具体来说:读指针不断往后移动。如果遇到非 0,则将读到的值写入写指针,触发写指针移动(其他情况写指针不动),读指针走到头算法结束。经过这样的处理,最终写指针的位置前面就是所有的非 0 数了, 最后将写指针后的 位置全部修改为 0 即可。

关键点解析

  • 读写双指针

代码

  • 语言支持:JS, C++, Java,Python
JavaScript Code:
1
/**
2
* @param {number[]} nums
3
* @return {void} Do not return anything, modify nums in-place instead.
4
*/
5
var moveZeroes = function (nums) {
6
let index = 0;
7
for (let i = 0; i < nums.length; i++) {
8
const num = nums[i];
9
if (num !== 0) {
10
nums[index++] = num;
11
}
12
}
13
14
for (let i = index; i < nums.length; i++) {
15
nums[index++] = 0;
16
}
17
};
Copied!
C++ Code:
解题思想与上面 JavaScript 一致,做了少许代码优化(非性能优化,因为时间复杂度都是 O(n)): 增加一个游标来记录下一个待处理的元素的位置,这样只需要写一次循环即可。
1
class Solution {
2
public:
3
void moveZeroes(vector<int>& nums) {
4
vector<int>::size_type nonZero = 0;
5
vector<int>::size_type next = 0;
6
while (next < nums.size()) {
7
if (nums[next] != 0) {
8
// 使用 std::swap() 会带来 8ms 的性能损失
9
// swap(nums[next], nums[nonZero]);
10
auto tmp = nums[next];
11
nums[next] = nums[nonZero];
12
nums[nonZero] = tmp;
13
++nonZero;
14
}
15
++next;
16
}
17
}
18
};
Copied!
Java Code:
1
class Solution {
2
public void moveZeroes(int[] nums) {
3
// 双指针
4
int i = 0;
5
for(int j=0; j<nums.length; j++)
6
{
7
// 不为0,前移
8
if(nums[j] != 0)
9
{
10
int temp = nums[i];
11
nums[i] = nums[j];
12
nums[j] = temp;
13
i++;
14
}
15
}
16
}
17
}
Copied!
Python Code:
1
class Solution:
2
def moveZeroes(self, nums: List[int]) -> None:
3
"""
4
Do not return anything, modify nums in-place instead.
5
"""
6
slow = fast = 0
7
while fast < len(nums):
8
if nums[fast] != 0:
9
nums[fast], nums[slow] = nums[slow], nums[fast]
10
slow += 1
11
fast += 1
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。