LeetCode面试题03.数组中的重复数【简知Offer】】【Easy】【Python】【数组】【哈希表】【排序】问题是找出数组中重复的数字。长度为n的数组nums中的所有数字都在0到n-1的范围内。数组中有些数字是重复的，但是不知道重复了多少个数字，也不知道每个数字重复了多少次。请找出数组中任何重复的数字。例1：输入：[2,3,1,0,2,5,3]输出：2or3限制：2<=n<=100000思路解1哈希表遍历数组，没有出现的flag为True，如果存在则返回该值。时间复杂度：O(n)，其中n是nums的长度。空间复杂度：O(n)，其中n是nums的长度。输入importListclass的Python3代码inrange(n):ifflag[nums[i]]==False:flag[nums[i]]=Trueelse:returnnums[i]return-1解2Sort先对数组排序，然后遍历，返回如果前一个数字相同，则为该值。时间复杂度：O(n)，其中n是nums的长度。空间复杂度：O(1)Python3代码来自输入importListclass解决方案：deffindRepeatNumber(self,nums:List[int])->int:#解决方案二：sortnums.sort()pre=nums[0]foriinrange(1,len(nums)):ifpre==nums[i]:returnnums[i]else:pre=nums[i]return-1解三个或两个萝卜一个坑遍历数组：1.如果位置的值和下标一样，不管他。2、如果带有position值的下标的值与position的值相同，则说明有重复，则返回该值。3.否则，将值与位置值的下标和位置值的时间复杂度交换：O(n)，n为nums的长度。空间复杂度：O(1)Python3代码来自输入importListclass解决方案：deffindRepeatNumber(self,nums:List[int])->int:#解决方案三n=len(nums)foriinrange(n):ifnums[i]==i:continue#repeatelifnums[nums[i]]==nums[i]:returnnums[i]#exchangeelse:nums[nums[i]],nums[i]=nums[i]],nums[nums[i]]返回-1代码地址GitHub链接
