这是崔斯特的第一百零八篇原创文章
努力、奋斗 (๑• . •๑)
找出数组中重复的数字
题目描述
在一个长度为 n
的数组里的所有数字都在 0
到 n-1
的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7
的数组 {2, 3, 1, 0, 2, 5, 3}
,那么对应的输出是重复的数字 2
或者 3
。
解法
解法一
排序后,顺序扫描,判断是否有重复,时间复杂度为 O(n²)
。
解法二
利用哈希表,遍历数组,如果哈希表中没有该元素,则存入哈希表中,否则返回重复的元素。时间复杂度为 O(n)
,空间复杂度为 O(n)
。
解法三
长度为 n
,元素的数值范围也为 n
,如果没有重复元素,那么数组每个下标对应的值与下标相等。
从头到尾遍历数组,当扫描到下标 i
的数字 nums[i]
:
- 如果等于
i
,继续向下扫描; - 如果不等于
i
,拿它与第nums[i]
个数进行比较,如果相等,说明有重复值,返回nums[i]
。如果不相等,就把第i
个数 和第nums[i]
个数交换。重复这个比较交换的过程。
此算法时间复杂度为 O(n)
,因为每个元素最多只要两次交换,就能确定位置。空间复杂度为 O(1)
。
|
|
代码中有一个两重循环,但每个数字最多只要交换两次就可以找到属于自己的位置,因此时间复杂度是O(n)。不需要额外分配内存,空间复杂度是O(1)。
Output
以数组[2, 3, 1, 0, 2, 5, 3]为例来分析找到重复数字的步骤:
- 数组的第 0 个数字(从 0 开始计数,和数组的下标保持一致)是 2,与它的下标不相等,于是把它和下标为 2 的数字 1 交换。交换之后的数组是[1, 3, 2, 0, 2, 5, 3]。
- 此时第 0 个数字是 1,仍然与它的下标不相等,继续把它和下标为 1 的数字 3 交换,得到数组[3, 1, 2, 0, 2, 5, 3]
- 接下来继续交换第 0 个数字 3 和第 3 个数字 0,得到数组[0, 1, 2, 3, 2, 5, 3]。
- 此时第 0 个数字的数值为 0,接着扫描下一个数字。在接下来的几个数字中,下标为 1,2,3 的三个数字分别为 1,2,3 它们的下标和数值都分别相等,因此不需要做任何操作。
- 接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等,再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2,也就是数字在下标为 2 和下标为 4 的两个位置都出现了,因此找到一个重复的数字。
本题关键是:在一个长度为 n
的数组里的所有数字都在 0
到 n-1
的范围内并且有重复,这说明数组是可以排序的,把每个数字交换到自己应该在的位置,排序时就能找到重复字段。理想状态下的情况:[0, 1, 2, 3, 4, x, x, x]
Python解法更简单
|
|
不修改数组找出重复的数字
题目描述
在一个长度为 n+1
的数组里的所有数字都在 1
到 n
的范围内,数组中至少有一个数字是重复的,请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为 8
的数组 {2, 3, 5, 4, 3, 2, 6, 7}
,那么对应的输出是重复的数字 2
或者 3
。
解法
解法一
创建长度为 n+1
的辅助数组,把原数组的元素复制到辅助数组中。如果原数组被复制的数是 m
,则放到辅助数组第 m
个位置。这样很容易找出重复元素。空间复杂度为 O(n)
。
解法二
数组元素的取值范围是 [1, n]
,对该范围对半划分,分成 [1, middle]
, [middle+1, n]
。计算数组中有多少个(count)元素落在 [1, middle]
区间内,如果 count
大于 middle
,那么说明这个范围内有重复元素,否则在另一个范围内。继续对这个范围对半划分,继续统计区间内元素数量。
时间复杂度 O(n * log n),空间复杂度 O(1)。
注意,此方法无法找出所有重复的元素。如果左右半区同时存在重复值,先算哪个半区就会先得到哪边的重复值。
|
|
按照二分法查找的思路,如果输出长度为n
的数组,那么函数countRange
将被调用O(log n)
次,每次需要O(n)
时间,因此总的时间复杂度是O(nlog n)
,空间复杂度是O(1)
。