找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字
时间: 2023-03-20 21:02:48 浏览: 168
找出数组中重复的数字.md
可以通过哈希表或者原地交换的方法来寻找重复数字。
1. 哈希表方法:
创建一个哈希表,遍历数组,如果当前数字已经在哈希表中存在,则说明这个数字是重复的,直接返回即可。如果当前数字不在哈希表中,则将当前数字作为键加入哈希表中。
2. 原地交换方法:
遍历数组,如果当前数字不等于其下标,则将其与对应下标的数字进行交换,直到该位置上的数字等于其下标。如果当前数字等于其下标,就继续遍历。如果在交换过程中发现有两个数字要被放到同一个位置,说明这个数字是重复的,直接返回即可。
代码示例(哈希表方法):
```python
def findDuplicate(nums):
dic = {}
for num in nums:
if num in dic:
return num
else:
dic[num] = 1
```
代码示例(原地交换方法):
```python
def findDuplicate(nums):
n = len(nums)
for i in range(n):
while nums[i] != i:
if nums[nums[i]] == nums[i]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
```
以上代码示例均为Python语言,可以直接复制粘贴运行。
阅读全文