【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]);

图解

1. 开始：

2. nums[cur]=0，不进入if条件，cur++。

3. nums[cur]=1，进入if条件，交换++dest和cur位置的元素

4. 然后cur++。

5. nums[cur]=0，不进入if条件，cur++。

6. nums[cur]=3，进入if条件，交换++dest和cur位置的元素

7. 然后cur++。

8. nums[cur]=12，进入if条件，交换++dest和cur位置的元素

9. 然后cur++。

   不满足cur < nums.size();跳出循环