给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路1:快排思想,左右两个指针,左指针负责找0,右指针找非0,找到后交换,指针相遇就停止,但是无法保证相对顺序,操作次数世界上最少,复杂度也是O(n),可惜了。
快排思想,不等于0的放左边,一轮扫描, 该方法:不能保证相对顺序,是快排思路
int left=0;
int right=nums.length-1;
while(left<right){
while(nums[left]!=0){//找零
left++;
}
while(nums[right]==0){//找非零
right--;
}
swap(nums,left,right);
left++;
right--;
}
int index=0;
思路2: 双指针,一个指针i全数组遍历,寻找非0元素,找到之后和第二个指针j交换,然后j++,这样保证[0,j)范围内的元素都是非0,全局遍历完之后就给[j,len)的元素补上0.
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
swap(nums,index++,i);
}
}
for(int i=index;i<nums.length;i++)nums[i]=0;
swap略,时间超越100%