|
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
思路1：数组
思路2：字典
思路3：set集合
思路4：原地置换算法
思路1：数组
只需要找到一个重复的数字即可，可以采用一个数组进行模拟，利用下标与数字对应，数组中的值作为出现次数。
时间和空间复杂度都是 O(n)
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
length = len(nums)
count = [0] * length
for i in range(length):
count[nums[i]] += 1
if count[nums[i]] > 1:
return nums[i]
return -1
思路2：字典
将上面的数组换成字典即可，依然可以统计次数.
时间复杂度：O(n)
空间复杂度：O(n), 应该比上面的数组要少。
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
length = len(nums)
count = {}
for i in range(length):
if nums[i] in count:
return nums[i]
else:
count[nums[i]] = 1
return -1
思路3：set集合
将上面的数组换成set集合即可，判断是否之前是否已经存在与集合即可.
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
length = len(nums)
count = set()
for i in range(length):
if nums[i] in count:
return nums[i]
else:
count.add(nums[i])
return -1
思路4：原地置换算法
这个方法非常巧妙，就一个根据题目知道：大小为N的数组中的数值是在[0,n-1]的，那么如果数组不重复，就应该可以一个下表对应一个数字，且是一一对应的即小标 i = num[i]的。所以我们就可以以用这一点进行判断，如果某一个下标对应了两个值那么就存在重复数字。
处理方法上：就是遍历数组，进行调整顺序，将i和nums[i]对应好，如果 i!=nums[i] 不相等，则需要将nums[i]放到下标为nums[i]的位置，并将下标为nums[i]上的值替换到下标为 i 的位置，如果此时 i 还不等于 nums[i] 时，继续上面的操作。
举例如下：
下表：0 1 2 3
值： 1 3 0 2
自己手动按照上面的处理方式演算以下即可领会。
此题的巧妙之处是不需要额外的存储空间，且时间与上面的基本一致，并且提供了一种特定环境下的排序方法。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
length = len(nums)
# 原地交换
for i in range(length):
while i != nums[i]: # 说明num[i]应该放到下标为num[i]的位置
if nums[nums[i]] == nums[i]: # 该位置已经匹配好了，则说明存在重复
return nums[i]
t = nums[nums[i]]
nums[nums[i]] = nums[i]
nums[i] = t
return -1
| 
转播
