LeetCode Hot100(4.移动零）

4.移动零题目给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入:nums [0,1,0,3,12]输出:[1,3,12,0,0]示例 2:输入:nums [0]输出:[0]解法一我们创建两个指针 i 和 j第一次遍历的时候指针 j 用来记录当前有多少 非0 元素。即遍历的时候每遇到一个 非0 元素就将其往数组左边挪第一次遍历完后j 指针的下标就指向了最后一个 非0 元素下标。第二次遍历的时候起始位置就从 j 开始到结束将剩下的这段区域内的元素全部置为 0。代码class Solution { public: void moveZeroes(vectorint nums) { int j0; for(int i0;inums.size();i){ if(nums[i]){ nums[j]nums[i]; } } for(int ij;inums.size();i){ nums[i]0; } } };解法二这里参考了快速排序的思想快速排序首先要确定一个待分割的元素做中间点 x然后把所有小于等于 x 的元素放到 x 的左边大于 x 的元素放到其右边。这里我们可以用 0 当做这个中间点把不等于 0(注意题目没说不能有负数)的放到中间点的左边等于 0 的放到其右边。这的中间点就是 0 本身所以实现起来比快速排序简单很多我们使用两个指针 i 和 j只要 nums[i]!0我们就交换 nums[i] 和 nums[j]代码这里参考了快速排序的思想快速排序首先要确定一个待分割的元素做中间点 x然后把所有小于等于 x 的元素放到 x 的左边大于 x 的元素放到其右边。这里我们可以用 0 当做这个中间点把不等于 0(注意题目没说不能有负数)的放到中间点的左边等于 0 的放到其右边。这的中间点就是 0 本身所以实现起来比快速排序简单很多我们使用两个指针 i 和 j只要 nums[i]!0我们就交换 nums[i] 和 nums[j]class Solution { public: void moveZeroes(vectorint nums) { int i0,j0; while(jnums.size()){ if(nums[j]){ swap(nums[i],nums[j]); i; } j; } } };