优先算法：双指针、移动零

优先算法：双指针、移动零

题目描述

移动零点击蓝色超链接即可跳转到题目详情

可以看到，以上题目给我们提了以下要求：

• 不能复制数组
• 将0移动到数组的末尾
• 保持非零元素的相对位置

算法原理

分析

以上的题目都可以归于一类：数组的划分（数组的分块）
解决这类问题，我们有一个非常经典的算法：双指针法

在数组中，我们使用数组下标来代替指针
即 arr[i] == parr + i

我们定义两个指针，一个是 cur 指向正在遍历的位置，它的前面是待处理的区域；第二个是 dest ，它的前面全是0，后面是非0元素。

如果 cur 指向的位置为0，就将数值与 dest + 1 的值进行交换，然后 dest++ ，直到 cur 指针指向n（即数组遍历完毕）。

总结

我们创建了两个指针 cur 与 dest
cur 在从前往后遍历的过程中

1. 遇到0元素: cur++;
2. 遇到非0元素: swap(dest + 1, cur); dest++; cur++;

编写代码

C语言

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void moveZeroes(int* nums, int numsSize) 
{
    for(int cur = 0, dest = -1; cur < numsSize; cur++)
    {
        if(nums[cur])
        {
            swap(&nums[++dest], &nums[cur]);
        }
    }    
}

C++

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int cur = 0, dest = -1; cur < nums.size(); cur++)
        {
            if(nums[cur])
                swap(nums[++dest], nums[cur]);
        }   
    }
};

写在最后

我们可以发现，此题的核心思想为数组的划分，与快速排序的核心算法分治法非常相似，我们仅需要将0与非0的判断替换为数值的比较，即可快速划分出小于等于tmp和大于tmp的部分。

如果你有更好的想法与思路，欢迎在评论区友好讨论，希望我的这篇文章能够抛砖引玉。感谢你的阅读。