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
|
|||
|
|
```
|