问题来源:move zeros
问题描述:给定一个数组,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
看到该问题第一个感觉很easy啊,抬手就来:
void moveZeroes(vector<int>& nums) {
int start=0,end=nums.size()-1;while(start<end){
while(start<end&&nums[start]!=0) start++;while(start<end&&nums[end]==0) end--;swap(nums[start],nums[end]);}
}
一运行居然错了,看输出结果一下明白过来了:上面的代码虽然把非0整数和0区分开了但是没有保证非0整数是顺序,还得重新构思。
要保持非0元素的相对顺序还只能从一侧遍历,一种思路是将遍历中遇到的0往后移,每遇到一个0就找一个非0与之交换,按照这个思路代码实现如下:
void moveZeroes(vector<int>& nums) {
int zeroIdx=0,nonZeroIdx;while(zeroIdx<nums.size()){
while(zeroIdx<nums.size()&&nums[zeroIdx]!=0) zeroIdx++;nonZeroIdx=zeroIdx+1;while(nonZeroIdx<nums.size()&&nums[nonZeroIdx]==0) nonZeroIdx++;if(nonZeroIdx>=nums.size()) return;swap(nums[zeroIdx],nums[nonZeroIdx]);zeroIdx++;}
}
上述代码一提交居然需要32ms,在超时的边缘徘徊,肯定有哪地方写得不好。如果仔细分析就会发现,当我们找到一个0元素之后都需要从该位置的下一个位置开始寻找非0元素。如果数组中的0元素很多,很大概率当前0元素的下一个位置还是0,我们还得重新遍历一遍0元素。这就启发我们不用每次都从当前位置的下一个位置开始遍历,而是从遍历到的非0元素的下一个位置开始遍历,这样就可以大大降低重复遍历的次数,按照这种逻辑修改上面的代码如下:
void moveZeroes(vector<int>& nums) {
int zeroIdx=0,nonZeroIdx=1;while(zeroIdx<nums.size()){
while(zeroIdx<nums.size()&&nums[zeroIdx]!=0) zeroIdx++;if(nonZeroIdx<zeroIdx) nonZeroIdx=zeroIdx+1;while(nonZeroIdx<nums.size()&&nums[nonZeroIdx]==0) nonZeroIdx++;if(nonZeroIdx>=nums.size()) return;swap(nums[zeroIdx],nums[nonZeroIdx]);zeroIdx++;nonZeroIdx++;}
}
上述代码提交之后运行需要12ms,超过了50%的用户,虽然有进步但感觉还是不够快。一时半会也没想到啥新的思路就翻翻题解吧,看完题解真是整个人都不好了,这么简单的题目居然让我整得这么复杂,看看题解代码吧:
void moveZeroes(vector<int>& nums) {
int nonZeroCount=0;for(auto n:nums){
if(n) nums[nonZeroCount++]=n;}for(int i=nonZeroCount;i<nums.size();i++){
nums[i]=0;}
}
之前代码的思路是先找0再去找非0,而题解代码是先找非0,找到非0直接覆盖前面的位置,找完之后后面直接赋0,就这么简单,运行时间可以进一步降低到8ms,超过92%的用户。无fuck说……