【C++习题】2.双指针_移动零
文章目录
- 题目链接：
- 题目描述：
- 解法（快排的思想：数组划分区间 - 数组分两块）：
- C++ 算法代码：
- 图解
题目链接：
283.移动零
题目描述：
解法（快排的思想：数组划分区间 - 数组分两块）：
双指针算法，利用数组下标充当指针。
我们可以用一个
cur指针来扫描整个数组，另一个dest指针用来记录非零数序列的最后一个位置。根据cur在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在
cur遍历期间，使[0, dest]的元素全部都是非零元素，[dest + 1, cur - 1]的元素全是零。
遇到0元素：
cur++遇到非0元素：
swap(dest+1, cur)
dest++, cur++
C++ 算法代码：
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
for(int cur = 0, dest = -1; cur < nums.size(); cur++)
if(nums[cur]) // 处理非零元素nums[cur]!=0
swap(nums[++dest], nums[cur]);
}
};
如果遇到0元素，cur++。也就是for(int cur = 0, dest = -1; cur < nums.size(); cur++)的末尾那句。
如果遇到非0元素，先swap(dest+1, cur)然后dest++, cur++。这里合并为 swap(nums[++dest], nums[cur]);
图解
- 开始：
nums[cur]=0，不进入if条件，cur++。
nums[cur]=1，进入if条件，交换++dest和cur位置的元素
- 然后
cur++。
nums[cur]=0，不进入if条件，cur++。
nums[cur]=3，进入if条件，交换++dest和cur位置的元素
- 然后
cur++。
nums[cur]=12，进入if条件，交换++dest和cur位置的元素
-
然后
cur++。不满足
cur < nums.size();跳出循环