题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7


给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

解题思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

一、审题 提取关键信息

1、输入 处理 输出  

输入:数组 数组为有序 （此题延申为数组无序时如何处理，如何效率更高）

处理：删除重复的元素

输出：处理过的数组长度

2、特殊条件 不使用额外的数组空间

考点可以为数组函数的使用

js中对数组本身进行操作的函数为split

java中为remove 等

官方处理 （双指针法）

数组不变 有序时每 后一个和前一个不等则 ++ return

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

复杂度分析

时间复杂度：O(n)O(n)， 假设数组的长度是 nn，那么 ii 和 jj 分别最多遍历 nn 步。

空间复杂度：O(1)O(1)。

实际实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var removeDuplicates = function(nums) {
    if(nums instanceof Array){
        if (nums.length == 0){
            return nums.length
        } 
        let idx = 0;
        while (idx < nums.length){
            if(nums[idx]==nums[idx+1]){
                nums.splice(idx,1);
            }else{
                idx++;
            }
        }
        return nums.length;
    }
};

1
2
3

var removeDuplicates = function(nums) {
    return nums.splice(0, nums.length, ...Array.from(new Set(nums))).length;
};
知识点

解构赋值 Array.from() new Set()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

解构赋值：语法是一个 Javascript 表达式，这使得可以将值从数组或属性从对象提取到不同的变量中。

Array.from(参数1,参数2，参数3)
1.想要转换成数组的伪数组对象或可迭代对象
2.新数组中的每个元素会执行该回调函数
3.执行回调里面的this指谁
返回一个新的数组实例


new Set([iterable]);
iterable：可迭代对象
返回：新的set对象

Go语言实现

在强制类型里面的构造和弱类型语言中不同，强制类型中的arr是不可以动态改变的，由此此题解法需要采用官方双指针法求解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func removeDuplicates(nums []int) int {
    if len(nums)==0 {
        return 0;
    }else{
        i := 0;
        j := 1;
        for i+j<len(nums) {
            if nums[i]==nums[j+i]{
                j++;
            }else{
                i++;
                nums[i] = nums[j+i-1];
            }
        }
        return len(nums)-j+1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func removeDuplicates(nums []int) int {
    length:=len(nums)
    var count int
    if length>0{
        count=1
    }
    maps:= map[int]int{}
    for i,v :=range nums{
        maps[v]=v
        for j:=i+1;j<length;j++{
            if _,ok:= maps[nums[j]];!ok{
                nums[i+1]=nums[j]
                maps[nums[j]]=nums[j]
                count++
                break
            }
        }
    }
    return count
}