[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:

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)。

--

--

Hi I am Samuel

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store