【LeetCode-简单】26.删除排序数组中的重复项

By 大Van家 on 2021-09-06
阅读时间 9 分钟
文章共 2.2k
阅读量

要点:数组、双指针、值传递与引用传递。

描述

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

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

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

1
2
3
输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素

提示:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

题解

复习JavaScript值传递与引用传递

JavaScript有5种基本的数据类型,分别是:布尔、null、undefined、String和Number。这些基本类型在赋值的时候是通过值传递的方式。值得注意的是还有另外三种类型: Array、Function和Object,它们通过引用来传递。从底层技术上看,它们三都是对象。

基本数据类型

如果一个基本的数据类型绑定到某个变量,我们可以认为该变量包含这个基本数据类型的值。

1
2
3
var x = 10;
var y = 'abc';
var z = null;

当我们使用=将这些变量赋值到另外的变量,实际上是将对应的拷贝了一份,然后赋值给新的变量。我们把它称作值传递

1
2
3
4
5
6
7
var x = 10;
var y = 'abc';

var a = x;
var b = y;

console.log(x, y, a, b) // 10, 'abc', 10, 'abc'

ax都包含10,by都包含'abc',并且它们是完全独立的拷贝,互不干涉。如果我们将a的值改变,x不会受到影响。

1
2
3
4
5
6
7
var x = 10;
var y = 'abc';
var a = x;
var b = y;
a = 5;
b = 'def';
console.log(x, y, a, b); // 10, 'abc', 5, 'def'

对象

如果一个变量绑定到一个非基本数据类型(Array, Function, Object),那么它只记录了一个内存地址,该地址存放了具体的数据。注意之前提到指向基本数据类型的变量相当于包含了数据,而现在指向非基本数据类型的变量本身是不包含数据的。

对象在内存中被创建,当我们声明arr = [],我们在内存中创建了一个数组。arr记录的是该内存的地址。

1
2
var arr = []; // (a)
arr.push(1); // (b)

当执行完(a)之后,内存中创建了一个空的数组对象,其内存地址为#001arr指向该地址。

变量 地址 对象
arr #001 []

引用传递

对象是通过引用传递,而不是值传递。也就是说,变量赋值只会将地址传递过去

1
2
var reference = [1];
var refCopy = reference;
变量 地址 对象
reference #001 [1]
refCopy #001

referencerefCopy指向同一个数组。 如果我们更新referencerefCopy也会受到影响。

1
2
reference.push(2);
console.log(reference, refCopy); // [1, 2], [1, 2]
变量 地址 对象
reference #001 [1, 2]
refCopy #001

引用重新赋值

如果我们将一个已经赋值的变量重新赋值,那么它将包含新的数据或者引用地址。

1
2
3
4
var obj = { first: 'yesmore.cc'};
obj = { second: 'aoau.top'};

console.log(obj) // { second: 'aoau.top' }

obj从指向第一个对象变为指向第二个对象。

变量 地址 对象
obj #001 {first: ‘yesmore.cc’}
#002 {second: ‘aoau.top’}

如果一个对象没有被任何变量指向,就如第一个对象(地址为#001),JavaScript引擎的垃圾回收机制会将该对象销毁并释放内存。

== 和 ===

对于引用类型的变量,=====只会判断引用的地址是否相同,而不会判断对象具体里属性以及值是否相同。因此,如果两个变量指向相同的对象,则返回true

1
2
3
4
var arrRef = ['Hi!'];
var arrRef2 = arrRef;

console.log(arrRef === arrRef2); // true

如果是不同的对象,即使包含相同的属性和值,也会返回false

1
2
3
4
var arr1 = ["Hi!"];
var arr2 = ["Hi!"];

console.log(arr1 === arr2); // false

如果想判断两个不同的对象是否真的相同,一个简单的方法就是将它们转换为字符串然后判断

1
2
3
4
var arr1str = JSON.stringify(arr1);
var arr2str = JSON.stringify(arr2);

console.log(arr1str === arr2str); // true

另一个方法就是递归地判断每一个属性的值,直到基本类型位置,然后判断是否相同。

函数参数

当我们将基本类型数据传入函数,函数会将这些数据拷贝赋值给函数的参数变量。

1
2
3
4
5
6
var hundred = 100;
var two = 2;
function multiply(x, y) {
return x * y;
}
var twoHundred = multiply(hundred, two);

hundred的值拷贝给变量xtwo的值拷贝给变量y

纯函数

对于一个函数,给定一个输入,返回一个唯一的输出。除此之外,不会对外部环境产生任何附带影响。我们机会称该函数为纯函数。所有函数内部定义的变量在函数返回之后都被垃圾回收掉。

但是,如果函数的输入是对象(Array, Function, Object),那么传入的是一个引用。对该变量的操作将会影响到原本的对象。这样的编程手法将产生附带影响,是的代码的逻辑复杂和可读性变低。

因此,很多数组函数,比如Array.mapArray.filter是以纯函数的形式实现。虽然它们的参数是一个数组变量,但是通过深度拷贝并赋值给一个新的变量,然后在新的数组上操作,来防止原始数组被更改。

我们来看一个例子:

1
2
3
4
5
6
7
8
9
10
11
function changeAgeImpure(person) {
person.age = 25;
return person;
}
var alex = {
name: 'Alex',
age: 30
};
var changedAlex = changeAgeImpure(alex);
console.log(alex); // { name: 'Alex', age: 25 }
console.log(changedAlex); // { name: 'Alex', age: 25 }

在非纯函数changeAgeImpure中,将对象personage更新并返回。原始的alex对象也被影响,age更新为25。

让我们来看如何实现一个纯函数

1
2
3
4
5
6
7
8
9
10
11
12
function changeAgePure(person) {
var newPersonObj = JSON.parse(JSON.stringify(person));
newPersonObj.age = 25;
return newPersonObj;
}
var alex = {
name: 'Alex',
age: 30
};
var alexChanged = changeAgePure(alex);
console.log(alex); // { name: 'Alex', age: 30 }
console.log(alexChanged); // { name: 'Alex', age: 25 }

我们通过JSON.sringify将对象变为一个字符串,然后再通过JSON.parse将字符串变回对象。通过该操作会生成一个新的对象。

面试题思考

值传递和引用传递经常在面试中被问到,来尝试回答一下如下代码如何输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function changeAgeAndReference(person) {
person.age = 25;
person = {
name: 'John',
age: 50
};

return person;
}
var personObj1 = {
name: 'Alex',
age: 30
};
var personObj2 = changeAgeAndReference(personObj1);
console.log(personObj1); // -> ?
console.log(personObj2); // -> ?

/*
{ name: 'Alex', age: 25 }
{ name: 'John', age: 50 }
*/

面试题思考:因为person.age=25是传递值所以影响到personObj1的age值,另一个是构造了一个新函数所以没有影响。

转自:https://www.cnblogs.com/xuniannian/p/9854599.html#top


关键点

实际上这就是双指针中的快慢指针。在这里快指针是读指针, 慢指针是写指针。

这道题如果不要求,O(n) 的时间复杂度, O(1) 的空间复杂度的话,会很简单。 但是这道题是要求的,这种题的思路一般都是采用双指针

  • 如果是数据是无序的,就不可以用这种方式了,从这里也可以看出排序在算法中的基础性和重要性。
  • 注意 nums 为空时的边界条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
if (nums.length == 0) return 0;
let slowP = 0;
for (let fastP = 0; fastP < nums.length; fastP++) {
if (nums[fastP] !== nums[slowP]) {
nums[++slowP] = nums[fastP];
}
}
return slowP + 1;
};
  • 362/362 cases passed (80 ms)
  • Your runtime beats 88.18 % of javascript submissions
  • Your memory usage beats 80.83 % of javascript submissions (40.1 MB)

时间复杂度:$O(N)$

空间复杂度:$O(1)$


Tips: Please indicate the source and original author when reprinting or quoting this article.