关于算法:数组一口气冲完快慢指针

7次阅读

共计 1548 个字符，预计需要花费 4 分钟才能阅读完成。

上篇文章讲了差分数组，这篇文章开始讲双指针技巧的快慢指针技巧。另外，数组有下图这些知识点与技巧。

通过两个指针来操作数组，通常利用在：1. 对数组有更改且不能建设新数组的状况下。2. 一次遍历实现需求。

另外，双指针类型有快慢指针，左右指针，滑动窗户，一般类型。

快慢指针模板

int 慢指针 = 0;
for (int 快指针 = 0; fast < nums.length; 快指针 ++) {if (快指针满足某个条件) {
        慢指针赋值操作
        慢指针右挪动操作
    }
}

leetcode 第 26 题

解题思路

套用模板，“快指针满足某个条件中的条件”：指快慢指针所指的元素不同。

最初返回值时，须要将慢指针 +1。

复杂度剖析

工夫复杂度：O(n)，n 是数组的长度。

空间复杂度：O(1)。

代码

class Solution {public int removeDuplicates(int[] nums) {
      int slow = 0;
      for (int fast = 0; fast < nums.length; fast++) {
         // 快慢指针所指元素不同
         if (nums[fast] != nums[slow]) {nums[++slow] = nums[fast];
         }
      }
      return slow + 1;
    }
}

leetcode 第 27 题

解题思路

套用模板，“快指针满足某个条件中的条件”：指快指针所指的元素与给定值不同。

复杂度剖析

工夫复杂度：O(n)，n 是数组的长度。

空间复杂度：O(1)。

代码

class Solution {public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // 快指针所指元素与 val 不同
            if (nums[fast] != val) {nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

leetcode 第 283 题

解题思路

套用模板，“快指针满足某个条件中的条件”：指快指针所指的元素不等于 0。

最初从在慢指针往后遍历数组，将遍历到的元素都赋值为 0。

复杂度剖析

工夫复杂度：O(n)，n 是数组的长度。

空间复杂度：O(1)。

代码

class Solution {public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {if (nums[fast] != 0) {nums[slow] = nums[fast];
                slow++;
            }
        }
        // 将满指针及前面的地位都赋值为 0
        for (int i = slow; i < nums.length; i++) {nums[i] = 0;
        }
    }
}

数组的快慢指针比较简单，另外链表也有快慢指针技巧。下一篇算法文章讲双指针之左右指针。