要点:数组、双指针、值传递与引用传递。
描述
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
1 | // nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝 |
示例 1:
1 | 输入:nums = [1,1,2] |
示例 2:
1 | 输入:nums = [0,0,1,1,1,2,2,3,3,4] |
提示:
- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums 已按升序排列
题解
复习JavaScript值传递与引用传递
JavaScript有5种基本的数据类型,分别是:布尔、null、undefined、String和Number。这些基本类型在赋值的时候是通过值传递的方式。值得注意的是还有另外三种类型: Array、Function和Object,它们通过引用来传递。从底层技术上看,它们三都是对象。
基本数据类型
如果一个基本的数据类型绑定到某个变量,我们可以认为该变量包含这个基本数据类型的值。
1 | var x = 10; |
当我们使用=
将这些变量赋值到另外的变量,实际上是将对应的值拷贝了一份,然后赋值给新的变量。我们把它称作值传递
。
1 | var x = 10; |
a
和x
都包含10,b
和y
都包含'abc'
,并且它们是完全独立的拷贝,互不干涉。如果我们将a
的值改变,x
不会受到影响。
1 | var x = 10; |
对象
如果一个变量绑定到一个非基本数据类型(Array, Function, Object),那么它只记录了一个内存地址,该地址存放了具体的数据。注意之前提到指向基本数据类型的变量相当于包含了数据,而现在指向非基本数据类型的变量本身是不包含数据的。
对象在内存中被创建,当我们声明arr = []
,我们在内存中创建了一个数组。arr
记录的是该内存的地址。
1 | var arr = []; // (a) |
当执行完(a)之后,内存中创建了一个空的数组对象,其内存地址为#001
,arr
指向该地址。
变量 | 地址 | 对象 |
---|---|---|
arr | #001 | [] |
引用传递
对象是通过引用传递,而不是值传递。也就是说,变量赋值只会将地址传递过去。
1 | var reference = [1]; |
变量 | 地址 | 对象 |
---|---|---|
reference | #001 | [1] |
refCopy | #001 |
reference
和refCopy
指向同一个数组。 如果我们更新reference
,refCopy
也会受到影响。
1 | reference.push(2); |
变量 | 地址 | 对象 |
---|---|---|
reference | #001 | [1, 2] |
refCopy | #001 |
引用重新赋值
如果我们将一个已经赋值的变量重新赋值,那么它将包含新的数据或者引用地址。
1 | var obj = { first: 'yesmore.cc'}; |
obj
从指向第一个对象变为指向第二个对象。
变量 | 地址 | 对象 |
---|---|---|
obj | #001 | {first: ‘yesmore.cc’} |
#002 | {second: ‘aoau.top’} |
如果一个对象没有被任何变量指向,就如第一个对象(地址为#001
),JavaScript引擎的垃圾回收机制会将该对象销毁并释放内存。
== 和 ===
对于引用类型的变量,==
和===
只会判断引用的地址是否相同,而不会判断对象具体里属性以及值是否相同。因此,如果两个变量指向相同的对象,则返回true
。
1 | var arrRef = ['Hi!']; |
如果是不同的对象,即使包含相同的属性和值,也会返回false
。
1 | var arr1 = ["Hi!"]; |
如果想判断两个不同的对象是否真的相同,一个简单的方法就是将它们转换为字符串然后判断。
1 | var arr1str = JSON.stringify(arr1); |
另一个方法就是递归地判断每一个属性的值,直到基本类型位置,然后判断是否相同。
函数参数
当我们将基本类型数据传入函数,函数会将这些数据拷贝赋值给函数的参数变量。
1 | var hundred = 100; |
hundred
的值拷贝给变量x
,two
的值拷贝给变量y
。
纯函数
对于一个函数,给定一个输入,返回一个唯一的输出。除此之外,不会对外部环境产生任何附带影响。我们机会称该函数为纯函数。所有函数内部定义的变量在函数返回之后都被垃圾回收掉。
但是,如果函数的输入是对象(Array, Function, Object),那么传入的是一个引用。对该变量的操作将会影响到原本的对象。这样的编程手法将产生附带影响,是的代码的逻辑复杂和可读性变低。
因此,很多数组函数,比如Array.map
和Array.filter
是以纯函数的形式实现。虽然它们的参数是一个数组变量,但是通过深度拷贝并赋值给一个新的变量,然后在新的数组上操作,来防止原始数组被更改。
我们来看一个例子:
1 | function changeAgeImpure(person) { |
在非纯函数changeAgeImpure
中,将对象person
的age
更新并返回。原始的alex
对象也被影响,age
更新为25。
让我们来看如何实现一个纯函数:
1 | function changeAgePure(person) { |
我们通过JSON.sringify
将对象变为一个字符串,然后再通过JSON.parse
将字符串变回对象。通过该操作会生成一个新的对象。
面试题思考
值传递和引用传递经常在面试中被问到,来尝试回答一下如下代码如何输出:
1 | function changeAgeAndReference(person) { |
面试题思考:因为person.age=25是传递值所以影响到personObj1的age值,另一个是构造了一个新函数所以没有影响。
转自:https://www.cnblogs.com/xuniannian/p/9854599.html#top
关键点
实际上这就是双指针中的快慢指针。在这里快指针是读指针, 慢指针是写指针。
这道题如果不要求,O(n) 的时间复杂度, O(1) 的空间复杂度的话,会很简单。 但是这道题是要求的,这种题的思路一般都是采用双指针
- 如果是数据是无序的,就不可以用这种方式了,从这里也可以看出排序在算法中的基础性和重要性。
- 注意 nums 为空时的边界条件。
代码
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.