use two index to reduce movements(C++)


  • 0
    F

    basic idea is i is always pointed to the first zero object, j is the first non-zero object after i
    initially we set j = i+1; after a iteration j = std::max(i+1,j);
    class Solution {
    public:
    void moveZeroes(vector<int>& nums) {
    int i = 0;
    int j = i+1;
    if (nums.size() < 1)
    {
    return;
    }
    while ( i < nums.size() -1 && j < nums.size())
    {
    while(nums[i]!=0 && i < nums.size()-1)
    {
    i++;
    }
    j= std::max(i+1,j);
    while (j < nums.size() && nums[j]==0)
    {
    j++;
    }
    if (i<nums.size()-1 && j < nums.size())
    {
    int temp = nums[j];
    nums[j] = nums[i];
    nums[i]= temp;
    }
    }
    }


Log in to reply
 

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