前情提要
数组可以说是最简单的一种数据结构,它占据一块连续的内存并按照顺序存储数据。创建数组时,需要指定数组的容量大小,然后根据大小分配内存。
存在的问题:空间效率不是很好。即使只在数组中存储一个数字,也需要为所有的数据预先分配内存,于是乎经常会有空闲的区域没有得到充分利用。
优势:由于数组的内存是连续的,于是可以根据下标在O(1)的时间内读写任何元素,因此时间效率是很高的。
⚠️注意:
- 数组下标都是从0开始的
- 数组内存空间的地址是连续的
为了解决数组空间效率不高的问题,人们又提出并实现了多种动态数组,在这里不再赘述。
寻找重复数
给定一个包含 n
个整数的数组 nums
,其数字都在 [0, n-1]
范围内,可知至少存在一个重复的整数。假设 nums
只有
一个重复的整数 ,返回 这个重复的数
。
方法一:排序
解决这个问题的一个简单方法就是把输入的数组排序,然后遍历查找即可。
排序一个数组的时间复杂度是 O(nlogn)
。
class Solution { |
- 时间复杂度:
O(nlogn)
- 空间复杂度:
O(1)
方法二:哈希表
还可以利用哈希表来解决这个问题,从头到尾按顺序遍历数组的每个元素,每扫描到一个元素时,都可以利用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字,就把它加入到哈希表;如果哈希表中已经存在了这个元素,就说明找到了答案。
class Solution { |
- 时间复杂度:
O(n)
- 空间复杂度:
O(n)
方法三:原地交换
注意到数组中的数字都在 [0, n - 1]
范围内,如果这个数组中没有重复的数值,那么当数组排序之后数字
i
将出现在下标为 i
的位置上。由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。
做法:重排数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为
i 的数字时,首先比较这个数字 m
是不是等于 i
,
如果是,接着扫描下一个数字;如果不是,则再拿它和第m
个数字进行比较。如果它和第
m
个数字相等,就找到了一个重复的数字,因为该数字在下标
i
和 m
的位置都出现了;如果它和第
m
个数字不相等,就把第 i
个数字和第
m
个数字交换,把 m
放到属于它的位置上。重复这个比较、交换的过程,直到发现第一个重复的数字。
举例:
nums = [2, 3, 1, 0, 2, 5, 3] |
代码:
class Solution { |
- 时间复杂度:
O(n)
,因为每个数字最多只要交换两次就能找到它的位置 - 空间复杂度:
O(1)
接下来我们提出一个要求:不修改数组,找出重复的数字,同时数组的范围变为了
[1,n]
,一共 n+1 个数。最简单的做法肯定是复制一份原始数组,然后就和上面说的一样了。
方法四:二分
核心重点的是理解在某个范围中的数字的个数。
把从 1~n 的数字从中间的数字 m 分为两部分,前面一半为
1~m
, 后面一半为 m+1~n
,如果 1~m
的数字的数目超过
m
,那么这一半的区间里一定包含重复的数字;否则另一半
m+1~n
的区间里一定包含重复的数字。可以继续把包含重复数字的区间一分为二,直到找到一个重复的数字。
举例:
nums = [2, 3, 5, 4, 3, 2, 6, 7] |
代码:
class Solution { |
- 时间复杂度:
O(nlogn)
,如果输入长度为n的数组,那么函数countRange
将被调用O(logn)次,每次需要O(n)的时间,因此总的时间复杂度是O(nlogn)
- 空间复杂度:
O(1)
好了,到此结束,四种思路,希望能够帮到你打开思路。我是youyi,我们下次见啦~