移动零算法(leetcode第283题)

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]
 

提示:

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

算法一：

思路：

双指针，分别指向0和非0数，然后分成小段的移位算法，将0移到小段末尾，右指针是从右边起第一个非0数。左指针是从右指针向左的第一个0

代码实现：

void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}
void moveZeroes(int* nums, int numsSize) {
    int *p=nums+numsSize-1,*q=nums+numsSize-1;
    //q-->寻找0,p-->框定右边界(p+1为0)
    //每次改变p，相当于缩小nums规模，化大为小
    //q最终指向p左边第一个0，并在p和q之间进行移位，将0移到p处
    while(1){
        if(p<nums) return;
        if(*p==0){//右边界左移
            p--,q--;
            continue;
        }
        else{
            //q寻找0
            while(*q!=0){
                if(q<=nums) return;
                q--;
            }
            while(1){
                //不断将0右移
                if(q==p) break;
                swap(q,q+1);//交换
                q++;
            }
            p--,q--;//右边界左移
        }
    }
}

算法优化：

思路：

代码实现：

void swap(int *a,int *b){
    int n = *a;
    *a = *b;
    *b = n;
}
//1 3 0 2 0 12 0 0 11
void moveZeroes(int* nums, int numsSize) {
    int left = 0; int right = 0;
    while(right < numsSize){
        if(nums[right]){//不为0
            swap(nums+left,nums+right);
            left ++ ;//left用来找左0
        }
        right ++;//right用来找left右边第一个非0数
    }
}