LeetCode 双刀流： 26. Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

「重复」的判断是一种常见的的问题，所以我们就选了这个题目 26. Remove Duplicates from Sorted Array，搭配我们前面的使用到的双指针技巧试试看。

先看一下题目描述

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

再搭配范例理解题目

• Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

• Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

该题目会给予一个「由小到大排序过」的阵列，要求在「同一个阵列中」，把重复的部分拿掉、不重复的元素往左移，剩下右边多余的来位置不计算。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：暴力法

第一个直觉的想法是利用其「排序过」的特性，利用隔壁的元素进行判断是否重复。这种方法可以利用 下一个元素 是否相同，若相同的话需要移除。

if nums[i] == nums[i+1]:
    nums.remove(nums[i])
}

那我们先用 Python 实作看看

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums)-1:
            if nums[i] == nums[i+1]:
                nums.remove(nums[i])
                i -= 1
            i += 1
            
        return len(nums)

也可以用 JavaScript 复刻一次

var removeDuplicates = function(nums) {
  for (i = 0; i < nums.length; i++) {
    if (nums[i] == nums[i+1]) {
      nums.splice(i, 1);
      i--;
    }
  }
  return nums.length;
};

方法 ②：双指针（Two Pointers）

第一个方法是利用下一个元素是否相同来判断是否重复，其实也可以改成利用前一个元素来判断。这个方法是往後找，只有找到跟 前一个元素 不重复的时候才需要加入。

count = 0
if nums[i] != nums[i-1]:
    nums[count] = nums[i]
    count = count + 1

仔细一看，这里我们用了两个变数 count 跟 i ，分别指向现在的元素（前一个元素）与下一个元素，用来比较是否不重复，这其实也是一种双指针（Two Pointers）的概念。

那我们先用 Python 实作看看

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        
        count = 1
        for i in range(1, len(nums)):
            if (nums[i] != nums[i-1]):
                nums[count] = nums[i]
                count += 1
        
        return count

也可以用 JavaScript 复刻一次

var removeDuplicates = function(nums) {   
  var count = 1;
  for(var i = 1 ; i < nums.length ; i++){
    if(nums[i] != nums[i-1]){
      nums[count] = nums[i];
      count++;
    }
  } 
  return count;
};

方法 ③：其他资料结构

讲到「重复」、「去除重复」类似的关键字，除了使用逻辑或流程的方法进行判断，也可以利用「资料结构」的特性。举例而言，在「Set」或「Map」的资料结构中，都有不重复的性质，因此第三种方法就是利用型态间转换来达到去除重复的效果。

那我们先用 Python 实作看看

// using dict as hashmap
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int: 
        map = {}
        for num in nums:
          map[num] = 1   
        nums = list(map.keys())
        return len(nums)

// set
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums = set(nums)
        return len(nums)

也可以用 JavaScript 复刻一次

// usgin object as hashmap
var removeDuplicates = function(nums) {
    map = {}
    for(let num of nums){
      map[num] = 1
    }
    nums = Object.keys(map);
    return nums.length;
};

// map
var removeDuplicates = function(nums) {
    map = new Map()
    for(let num of nums){
      map.set(num, 1);
    }
    nums = Array.from(map.keys());
    return nums.length;
};

// set
var removeDuplicates = function(nums) {
    nums = [...new Set(nums)];
    return nums.length;
};

虽然这几种资料结构执行的结果可以满足题目的要求，但实际上是过不了测试的。主要的原因在於题目的描述中有一句话：「remove the duplicates in-place such that each unique element appears only once」，当中的 in-place 的意思是 不能更动到原有阵列的起始位置 ，也就是说不能对 nums 重新赋值。

反思沉淀

重复的判断是一种常见的的问题，透过这个题目我们尝试「逻辑与流程控制」与「善用资料结构特性」两种方法来实现。虽然本题有一些限制必须一定要用「逻辑与流程控制」，但实务上「善用资料结构特性」也是一种可行的路。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 27. Remove Element
• 80. Remove Duplicates from Sorted Array II
• 442. Find All Duplicates in an Array
• 83. Remove Duplicates from Sorted List
• 82. Remove Duplicates from Sorted List II

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。