[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;
}

Explanation:

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