双指针-快慢指针

• 快慢指针：快慢指两个指针每次移动的步长，比如慢指针每次移动一步，快指针每次移动两步。

• 例题：LeetCode283：移动零

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

  • 例：输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

  • 思路1：设两个指针，一个遍历数组，一个只在元素非零时用于给数组赋值。最后再将数组剩下的位置全部填0

  • 代码：

    class Solution {
    public:
        /*按顺序为数组赋值原数组的正数即可*/
        void moveZeroes(vector<int>& nums) {
            int j = 0;
            for(int i = 0;i < nums.size(); ++i)
                if(nums[i] != 0)
                    nums[j++] = nums[i];
            while(j < nums.size())
                nums[j++] = 0;
        }
    };

  • 思路2：由于数组每个非零数，正确位置要么在当前位置，要么在此位置之前，所以可设快慢指针，每次遇到非零数时，直接交换两个指针指向的元素。相比思路1，避免了数组前导数全为0时的多余操作。

  • 代码：(此源代码来自LeetCode官方)

    class Solution {
    public:
        /*快慢指针
        *当前数的位置最多不动或该往前移动
        */
    	void moveZeroes(vector<int>& nums) {
            for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
                if (nums[cur] != 0) {
                    swap(nums[lastNonZeroFoundAt++], nums[cur]);
                }
            }
         }
    };