在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组[2,3,1,0,2,5,3],那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围:
进阶:时间复杂度,空间复杂度
[2,3,1,0,2,5,3]
2
2或3都是对的
class Solution: def duplicate(self , numbers: List[int]) -> int: # write code here length = len(numbers) for i in range(length): while (numbers[i] != i): if numbers[i] == numbers[numbers[i]]: return numbers[i] # 交换顺序反了会超时,莫名其妙 numbers[numbers[i]],numbers[i] = numbers[i],numbers[numbers[i]] return -1
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param numbers int整型一维数组 # @return int整型 # from typing import List class Solution: @staticmethod def duplicate(numbers: List[int]) -> int: if not numbers: return -1 for num in numbers: if num < 0&nbs***bsp;num > len(numbers) - 1: return -1 for i in range(len(numbers)): idx = abs(numbers[i]) if numbers[idx] < 0: return idx numbers[idx] = -numbers[idx] return -1 def duplicate_next(self, numbers: List[int]) -> int: # 哈希表记录重复 mp = dict() # 遍历数组 for num in numbers: # 如果没有出现过就加入哈希表 if num not in mp: mp[num] = num # print(mp[num]) # 否则就是重复数字 else: return num # 没有重复 return -1 instance = Solution() number = [2, 3, 1, 0, 2, 5, 3] # print(instance.duplicate(number)) # 输出 2 或 3
import random class Solution: def duplicate(self , numbers: List[int]) -> int: # write code here list1 = [] list2 = [] for i in numbers: if max(numbers)>len(numbers): break elif i not in list1: list1.append(i) elif i in list1: list2.append(i) if len(list2) > 0: return (random.choice(list2)) elif len(list1) == 0 and len(list2) == 0: return (-1) else: return '无重复数据'