283. Move Zeroes - cocoder39/coco39_LC GitHub Wiki

283. Move Zeroes

Suppose there are a non0-zero and b zero in array. each swap takes three write operation, at most write 3a times. Write less if using if (nums[j] != 0 && j != i). If a >> b, you can either use two pointers points to start and end of array and do swap (solution 2), which takes 3 * min(a, b) = 3b writes, or start from the end, swap zero (solution 3), which takes 3b writes. But both methods is not stable, clarify with interviewer if you can change the relative order of non-zeros.

solution 1:

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

public void moveZeroes(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                if (nums[i] == 0) {
                    nums[i] = nums[j];
                    nums[j] = 0;
                } 
                i++;
            }
        }   
    }

Method below guarantee (a+b) times write.

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

further decrease write operaions

solution 4:

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

Conclusion:

  • if stability is required:

if 3a < (a+b) => 2a < b => solution 1

else => solution 4

  • if stability is not required:

if a << b => solution 1 or 3

if a >> b => solution 2 or 3

n < 3a && n < 3b => a > n/3 && b > n/3 => solution 4

⚠️ **GitHub.com Fallback** ⚠️