题目要求
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数
方法1:
因为刚学了插入排序,所以 就按照那个思路
从后往前,遇到0,就把它之后的所有数字往前一格,然后0填充末尾
class Solution { public: void moveZeroes(vector<int>& nums) { for(int i=nums.size()-2;i>=0;i--){ if(nums[i]!=0) continue; int j=i; for(;j<nums.size()-1;j++){ if(nums[j+1]==0) break; nums[j]=nums[j+1]; } nums[j]=0; } } };
方法2:(较好)
双指针,都从0开始
右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。
去看下leetcode的题解吧
class Solution { public: void moveZeroes(vector<int>& nums) { int left=0,right=0; while(right<nums.size()){ if(nums[right]!=0){ swap(nums[left],nums[right]); left++; } right++; } } };