算法题/双指针：移除重复

题目

给定一个已排序的数字数组，从其中删除所有重复项。你不应该使用任何额外的空间;在原地删除重复项后，返回没有重复项的子数组的长度。

相似问题 ：给定一个未排序的数字数组和一个目标值key，删除所有key的实例，并返回数组的新长度。

示例1：

输入：[2, 3, 3, 3, 6, 9, 9]
输出：4
解释：移除重复元素后，剩余元素为[2, 3, 6, 9]

示例2：

输入：[2, 2, 2, 11]
输出：2
解释：移除重复元素后，剩余元素为[2, 11]

解法1：双指针

Java

class RemoveDuplicates {

  public static int remove(int[] arr) {
    int nextNonDuplicate = 1; //下一个非重复元素的索引
    for (int i = 1; i < arr.length; i++) {
      if (arr[nextNonDuplicate - 1] != arr[i]) {
        arr[nextNonDuplicate] = arr[i];
        nextNonDuplicate++;
      }
    }

    return nextNonDuplicate;
  }

  public static void main(String[] args) {
    int[] arr = new int[] { 2, 3, 3, 3, 6, 9, 9 };
    System.out.println(RemoveDuplicates.remove(arr));

    arr = new int[] { 2, 2, 2, 11 };
    System.out.println(RemoveDuplicates.remove(arr));
  }
}

JavaScript

class RemoveDuplicates {
  static remove(arr) {
    let nextNonDuplicate = 1; // 下一个非重复元素的索引
    for (let i = 1; i < arr.length; i++) {
      if (arr[nextNonDuplicate - 1] !== arr[i]) {
        arr[nextNonDuplicate] = arr[i];
        nextNonDuplicate++;
      }
    }

    return nextNonDuplicate;
  }
}

let arr = [2, 3, 3, 3, 6, 9, 9];
console.log(RemoveDuplicates.remove(arr));

arr = [2, 2, 2, 11];
console.log(RemoveDuplicates.remove(arr));

Python

class RemoveDuplicates:
    def remove(arr):
        nextNonDuplicate = 1  # 下一个非重复元素的索引
        for i in range(1, len(arr)):
            if arr[nextNonDuplicate - 1] != arr[i]:
                arr[nextNonDuplicate] = arr[i]
                nextNonDuplicate += 1

        return nextNonDuplicate


arr = [2, 3, 3, 3, 6, 9, 9]
print(RemoveDuplicates.remove(arr))

arr = [2, 2, 2, 11]
print(RemoveDuplicates.remove(arr))

Go

package main

import "fmt"

func remove(arr []int) int {
	nextNonDuplicate := 1 // 下一个非重复元素的索引
	for i := 1; i < len(arr); i++ {
		if arr[nextNonDuplicate-1] != arr[i] {
			arr[nextNonDuplicate] = arr[i]
			nextNonDuplicate++
		}
	}

	return nextNonDuplicate
}

func main() {
	arr := []int{2, 3, 3, 3, 6, 9, 9}
	fmt.Println(remove(arr))

	arr = []int{2, 2, 2, 11}
	fmt.Println(remove(arr))
}