LeetCode283 Move Zeroes

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

样例

1
2
For example, given nums = [0, 1, 0, 3, 12], 
after calling your function, nums should be [1, 3, 12, 0, 0].

思路

给一个数组,现在要把所有0都移到数组的末尾,其他非零数字的相对顺序不能改变。

考虑双指针,令l为答案数组的指针,r为原数组的指针。r在移动到一个非零的数时,把它和l指向的位置的元素进行交换。

为什么可以交换呢?因为此时l指向的位置的元素只有两种情况,要么nums[l] == nums[r] (或者说是l == r) 要么 nums[l] == 0。因此交换之后就相当于把0往后移了。

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int size = nums.size(), l = 0, r = 0;
while (r < size) {
if (nums[r]) swap(nums[l++], nums[r]);
r++;
}
}
};
分享到 评论