第一反应只会写冒泡的,但是注意要从后往前冒泡,每遇到一个0就一直向后交换,直到最后,不然遍历的时候会把未遍历到的0的位置改变,导致缺失,贴代码。
class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(); int temp; for(int i = n-2 ; i >=0 ; i--) { if(nums[i] == 0) { for(int j = i ; j <n-1 ; j++) { swap(nums[j],nums[j+1]); } } } } };
nnd,双指针很巧妙,以0为标准,将所有不是0的数放到0的左边,0都放到右边,解决问题,贴代码
class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(); int right = 0; int left = 0; while(right<n) { if(nums[right]) { swap(nums[right],nums[left]); left++; } right++; } } };
这种解法有一个问题就是会有很多无效操作,如前几个元素都不为0的话,要每个元素和自己交换一下,是废操作。想了一下,可以每次遍历,找到当前第一个0,以及这个0之后的第一个非零数,进行交换。