力扣-283移动零-双指针

力扣-283移动零-双指针

• • —、题目解析
  • 二、解题思路
  • 三、代码实现

—、题目解析

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]

二、解题思路

以数组nums = [0,1,0,3,12]为例，我们定义两个变量cur和dest将数组分为三部分，保证[0,dest]全为非0元素，
[dest+1,cur-1]全为0元素，[cur,numSize-1]为未处理元素，cur从左往右遍历数组，当遇到0元素cur++，遇到
非0元素swap(dest+1,cur),dest++,cur++。这个过程和快速排序中找一个中间变量temp,将数组分为两部分，temp前面部分数字小于temp，后面部分数字大于temp。

三、代码实现

C语言实现

void moveZeroes(int* nums, int numsSize)
{
	int left=-1;
	int right=0;
	for(right=0;right<numsSize;right++)
	{
		if(nums[right]!=0)
		{
			left++;
			int temp=nums[left];
			nums[left]=nums[right];
			nums[right]=temp;
		}
	}
} 

Java实现

class Solution {
    public void moveZeroes(int[] nums) 
    {
     for(int cur=0,dest=-1;cur<nums.length;cur++)
     {
        if(nums[cur]!=0)
        {
            dest++;
            int temp=nums[dest];
            nums[dest]=nums[cur];
            nums[cur]=temp;
        }
     }
    }
}

其他写法

void moveZeroes(int* nums, int numsSize) 
 {
     int *arr=calloc(sizeof(int),numsSize);
     int i=0;
     int j=0;
     for(i=0;i<numsSize;i++)
     {
 		if(nums[i]!=0)
 		{
 			arr[j++]=nums[i];
 		}
 	}
 	for(int i=0;i<numsSize;i++)
 	{
 		nums[i]=arr[i];
 	}
 }

欢迎留言讨论。