283. Move Zeroes

Posted on Edited on In

283. Move Zeroes

Description

Difficulty: Easy

Related Topics: Array, Two Pointers

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

1
2
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

1
2
Input: nums = [0]
Output: [0]

Constraints:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

Hints/Notes

  • 2023/08/04
  • Remove the element first, then set the remaining to zero
  • 0x3F’s solution(checked)

Solution

Language: C++

Cleaner solution:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int idx = 0;
        for (int& x : nums) {
            if (x) {
                swap(nums[idx++], x);
            }
        }
    }
};

My solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = removeElement(nums, 0);
        for (int i = len; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val) {
        int fast = 0, slow = 0, len = nums.size();
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }
};