【优选算法篇】leetcode算法题

前言

什么是双指针？

用最通俗的语言来讲所谓双指针算法是针对于遍历的过程的，我们平常在用for循环遍历的时候都是用单个指针在进行循环访问，而双指针就是用两个相同方向的或者相反方向的指针进行扫描，从而达道算法的目的。比如在一层循环里同时设置 i,j两个变量。 换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算，将时间复杂度从log(n^2)降到log(n)。 注意：这里的指针，并非专指C语言中指针的概念，而是指索引，游标或指针，可迭代对象等！

核心思想

有重复计算的区间，用双指针优化。将上一个状态指针所表达的信息传递至下一状态，减少无谓的搜索。

题目1：移动零

题目链接：283. 移动零 - 力扣（LeetCode）

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

解决思路：

本题巧妙使用双指针算法。

1.初始化两个指针：

。cur: 用于遍历整个数组。

。dest：指向最后一个非零元素，初始化为-1。

2.遍历数组

。如果cur指向非零元素，将dest+1，同时将两个指针对应元素进行交换。

。当cur指向元素为零，不做任何操作，将cur+1。

3. 结束条件

当cur走向最后一个位置为止。

图解：

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

复杂度分析：

时间复杂度为O（n），空间复杂度O（1）。