leetcode–python–剑指offer03

找出数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = set() 		#首先创建一个集合
        for i in nums:		#遍历nums
            if i in dic:	#如果在dic集合，返回，break
                return(i)
                
            else:			#否则将i添加到集合
                dic.add(i)

另一种方法，用的原地交换法：就是将nums的下标和nums元素对应，将nums下标等于nums元素对应的值，如果有重复就返回元素

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
       
        for i in range(len(nums)):#遍历nums
            if nums[i] == i:					#如果下标i对应的元素等于i，则跳过
                continue
            if nums[nums[i]] == nums[i]:		#证明nums[i]不止出现一次，返回
                return(nums[i])
            nums[nums[i]] = nums[i]				#否则，将nums中下标i对应的值赋值给该值所对应的nums的下标元素值，这样如果下次num[i]等于nums[nums[i]]，证明nums[i]不止出现一次，返回
                

本文地址：https://blog.csdn.net/AWhiteDongDong/article/details/110425303