LC283, Move Zeroes, Two pointers


  • 0
    N
    1. Two pointers
      Time Complexity : O(N);
    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0, len = nums.size();
        while (i < len && nums[i] != 0) {
            i++;
        }
        
        j = i + 1;
        while (j < len) {
            if (nums[j] != 0) {
                swap(nums[i], nums[j]);
                i++;
            }
            
            j++;
        }
        
        return;
    }
    

    This is my first version code. Algorithm is simple , i and j are pointers with same moving direction.
    [0, i) does not have zero.
    [i, j] all zero elements

    2 optimization
    Last approach is good, however the code looks very ugly. so How to just optimize code style. "Swap with itself" is ok !!!
    When we think about "swap", we always think swap two different entries. Actually swap with itself is also fine.

    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0;
        for (; j < nums.size(); j++) {
            if (nums[j] != 0) {
                //exchange
                swap(nums[i], nums[j]);
                i++;
            }
        }
    }
    

    This code are much cleaner now

    3 No swap approach, clever observation
    https://discuss.leetcode.com/topic/24716/simple-o-n-java-solution-using-insert-index
    the solution of the link is very smart. It takes advantages of the fact that 0 is placed the latter part of array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.