Move Zeroes
描述:
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
1.You must do this in-place without making a copy of the array.
2.Minimize the total number of operations.
思路:在保持原有数组顺序的情况下把0去掉。不能新建数组,最小化操作步数。遍历数组,遇到0做一个标记,然后继续向下遍历遇到第一个非0的再做一个标记,将这两个位置互换。重复该操作。
问题:
要注意第二层for循环中的判断条件应该有两个,j<numsSize&&nums[j]==0,如果只有后一个会出现数组读取越界的情况并与数组外的非零值进行交换,因而要加上数组的长度边界判断。
同时,如果不做优化的话这样的运行速度会很低,因此进行了两步优化。一是在第二层for循环中判断并赋予j开始的值,使其减少重复比较;二是加入flag标志目的在于在第二层for循环的某一次中若已经遍历完成数组,则直接跳出循环,避免了第一层for循环执行的重复。确实提高了运行速度,但是相对而言还是较慢。
代码:
void moveZeroes(int* nums, int numsSize) {
int i;
int j=0;
int temp;
int p;
int q=0;
for(i=0;i<numsSize;i++){
if(nums[i]==0){
p=i;
if(p>j){
q=p;
}
else{
q=j;
}
for(j=q+1;(j<numsSize&&nums[j]==0);){
j++;
}
int flag=1;
if(j<numsSize){
temp=nums[j];
nums[j]=nums[i];
nums[i]=temp;
flag=0;
}
if(flag)
return;
}
}
}