100 lines
2.5 KiB
Markdown
100 lines
2.5 KiB
Markdown
|
||
## 题目地址
|
||
https://leetcode.com/problems/move-zeroes/description/
|
||
|
||
## 题目描述
|
||
```
|
||
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
|
||
|
||
Example:
|
||
|
||
Input: [0,1,0,3,12]
|
||
Output: [1,3,12,0,0]
|
||
Note:
|
||
|
||
You must do this in-place without making a copy of the array.
|
||
Minimize the total number of operations.
|
||
|
||
```
|
||
## 思路
|
||
|
||
如果题目没有要求 modify in-place 的话，我们可以先遍历一遍将包含 0 的和不包含 0 的存到两个数组，
|
||
然后拼接两个数组即可。 但是题目要求 modify in-place， 也就是不需要借助额外的存储空间，刚才的方法
|
||
空间复杂度是 O(n).
|
||
|
||
那么如果 modify in-place 呢？ 空间复杂度降低为 1。
|
||
|
||
我们可以借助一个游标记录位置，然后遍历一次，将非 0 的原地修改，最后补 0 即可。
|
||
|
||
## 关键点解析
|
||
|
||
无
|
||
|
||
## 代码
|
||
|
||
* 语言支持：JS, C++, Python
|
||
|
||
JavaScript Code:
|
||
|
||
```js
|
||
/**
|
||
* @param {number[]} nums
|
||
* @return {void} Do not return anything, modify nums in-place instead.
|
||
*/
|
||
var moveZeroes = function(nums) {
|
||
let index = 0;
|
||
for(let i = 0; i < nums.length; i++) {
|
||
const num = nums[i];
|
||
if (num !== 0) {
|
||
nums[index++] = num;
|
||
}
|
||
}
|
||
|
||
for(let i = index; i < nums.length; i++) {
|
||
nums[index++] = 0;
|
||
}
|
||
};
|
||
```
|
||
|
||
C++ Code：
|
||
|
||
> 解题思想与上面 JavaScript 一致，做了少许代码优化（非性能优化，因为时间复杂度都是 O(n)）：
|
||
> 增加一个游标来记录下一个待处理的元素的位置，这样只需要写一次循环即可。
|
||
|
||
```C++
|
||
class Solution {
|
||
public:
|
||
void moveZeroes(vector<int>& nums) {
|
||
vector<int>::size_type nonZero = 0;
|
||
vector<int>::size_type next = 0;
|
||
while (next < nums.size()) {
|
||
if (nums[next] != 0) {
|
||
// 使用 std::swap() 会带来 8ms 的性能损失
|
||
// swap(nums[next], nums[nonZero]);
|
||
auto tmp = nums[next];
|
||
nums[next] = nums[nonZero];
|
||
nums[nonZero] = tmp;
|
||
++nonZero;
|
||
}
|
||
++next;
|
||
}
|
||
}
|
||
};
|
||
```
|
||
|
||
Python Code:
|
||
|
||
```python
|
||
class Solution:
|
||
def moveZeroes(self, nums: List[int]) -> None:
|
||
"""
|
||
Do not return anything, modify nums in-place instead.
|
||
"""
|
||
slow = fast = 0
|
||
while fast < len(nums):
|
||
if nums[fast] != 0:
|
||
nums[fast], nums[slow] = nums[slow], nums[fast]
|
||
slow += 1
|
||
fast += 1
|
||
```
|