移动零算法(leetcode第283题)

发布时间:2023年12月17日

题目描述:

给定一个数组 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数
    }
}

文章来源:https://blog.csdn.net/Xudong_12345/article/details/135049577
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。