Monday, July 4, 2016

Moves Zero

Problem:
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.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        int iter = 0;
        for (int zero_iter = 0; zero_iter < size; zero_iter++) {
            if (nums[zero_iter] != 0) {
                nums[iter++] = nums[zero_iter];
                if (iter - 1 == zero_iter) {
                    // Iter == zero_iter means base case: no zero till now.
                    continue;
                }
                nums[zero_iter] = 0;
            }
        }
        return;
    }
};

===== Another =====

void moveZeroes(vector<int>& nums) {
        int count = 0, iter = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                nums[iter++] = nums[i];
            }
        }
        for (int i = iter; i < nums.size(); i++) {
            nums[i] = 0;
        }
        return;
    }

No comments:

Post a Comment