题目内容
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例1:
- 输入：
[2, 3, 1, 0, 2, 5, 3] - 输出：
2 或 3
- 输入：
限制：
- 2 <= n <= 100000
解题思路
哈希表
- 定义一个哈希表
set - 遍历数组
nums，每个数字为num- 如果
num在set中，说明num重复，直接返回num - 如果
num不在set中，set添加num
- 如果
- 没有重复的，返回-1
原地交换
- 遍历数组
nums，依照索引下标- 若
nums[i] = i： 说明此数字已在对应索引位置，无需交换，因此跳过 - 若
nums[nums[i]] = nums[i]： 代表索引nums[i]处和索引i处的元素值都为nums[i]，即找到一组重复值，返回此值nums[i] - 否则，交换 索引
i和nums[i]的值，即nums[nums[i]] = nums[i], nums[i] = nums[nums[i]]
- 若
- 遍历完还没有重复项，则返回
-1
代码解法
Java
class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while(i != nums[i]) {
if (nums[nums[i]] == nums[i]) {
return nums[i];
}
int tmp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = tmp;
}
}
return -1;
}
}
Python
from typing import List
class Solution:
# 哈希表，判断是否存在
def findRepeatNumber(self, nums: List[int]) -> int:
map = set()
for num in nums:
if num in map:
return num
map.add(num)
return -1
# 原地交换
def findRepeatNumber2(self, nums: List[int]) -> int:
i = 0
while i < len(nums):
if nums[i] == i:
i += 1
continue
if nums[nums[i]] == nums[i]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
return -1