做网站查询违章,dedecms 门户网站制作,品牌设计公司排名品牌形象广告,wordpress 企业题目描述#xff1a;
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: n…题目描述
给定一个数组 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;*btemp;
}
void moveZeroes(int* nums, int numsSize) {int *pnumsnumsSize-1,*qnumsnumsSize-1;//q--寻找0,p--框定右边界(p1为0)//每次改变p相当于缩小nums规模化大为小//q最终指向p左边第一个0并在p和q之间进行移位将0移到p处while(1){if(pnums) return;if(*p0){//右边界左移p--,q--;continue;}else{//q寻找0while(*q!0){if(qnums) return;q--;}while(1){//不断将0右移if(qp) break;swap(q,q1);//交换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]){//不为0swap(numsleft,numsright);left ;//left用来找左0}right ;//right用来找left右边第一个非0数}
}
