双指针算法

February 27, 2019

下面三个算法都可以使用“双指针”就地操作来实现:

  1. 数组去除某元素。如输入 [4,2,3,4,1,2,4][4,2,3,4,1,2,4] 去除其中的 44

  2. 有序数组去重。如输入 [0,0,1,1,2,2,2,3][0,0,1,1,2,2,2,3],输出 [0,1,2,3][0,1,2,3]

  3. Quicksort 算法中的 partition 操作。

其共同点在于,它们都是把“符合情况的”挪到数组前面。双指针的其中一个代表已经处理好的元素,另一个代表等待处理的元素。

function removeElement(nums, val) {
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] !== val) {
      nums[i] = nums[j];
      i += 1;
    }
  }
  return i;
};

如上数组去除某元素的算法的不变量是:

(0,i)(0,i) 代表已经处理好,即不含 val 值的元素,[j,nums.length)[j, nums.length) 代表未处理的元素。

开始时 i=0, j=0i=0,~j=0(0,0)(0,0) 为空,[0,nums.length)[0, nums.length) 为整个列表。开始 for 循环,每次判断 j 指向的元素:

如果不等于 val,那么我们获得了一个已经处理好的元素,把它拷贝到 i 指针的位置,已处理好的元素从 (0,i)(0,i) 变为了 (0,i](0,i],即 (0,i+1)(0,i+1)i 进一位;如果等于 val,不做任何操作。

循环后 j 指针进一位,即未处理的元素变为了 [j+1,nums.length)[j+1, nums.length)

因此每次循环后不变量仍然成立。当循环结束时,(0,i)(0,i) 即为数组中所有异于 val 的元素。

nn 个元素的数组中如果有 mm 个异于 val 的值,按照上面的方法需要执行 mm 次复制操作。如果数组中几乎都是异于 val 的值,如下方法把不符合要求的值挪到后边丢弃掉,可以将复制操作减少到 nmn-m 次:

function removeElement(nums, val) {
  let i = 0;
  let j = nums.length - 1;
  while (i <= j) {
    if (nums[i] === val) {
      nums[i] = nums[j];
      j--;
    } else {
      i++;
    }
  }
  return i;
}

其中不变量为: (0,i)(0,i) 代表异于 val 的元素,(j,nums.length)(j, nums.length) 代表丢弃的元素,[i,j][i,j] 代表未处理的元素。当未处理的元素为空时结束循环。