[Leetcode 283]Move Zeros

Description:

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:

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

Example 2:

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

Constraints:

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

C code soultion:

void swap(int* a, int* b){
    if(a == b)
        return;
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}
void moveZeroes(int* nums, int numsSize){
    int write_idx = 0;
    for(int i=0; i<numsSize; i++){
        if(nums[i] != 0){
            swap(&nums[write_idx], &nums[i]);
            write_idx++;
        }
    }
}

Explanation:

遇到非零的數直接與 write_idx 這個位置交換，交換完後 write_idx 會加一，write_idx 會從0開始。由於非零的數會按照原本順序塞到最前面，而零則不會，所以所有零會自動塞在最後側。此方法為O(n)。