[数据结构与算法]Leetcode001_Easy：找出数组中重复的数字

我的解法：

class Solution(object):
   def findRepeatNumber(self, nums):
       """
       :type nums: List[int]
       :rtype: int
       """
       dic= set()
       for num in nums:
           if num in dic:return num
           dic.add(num)
       return -1

时间复杂度：O（n）
空间复杂度：O（n）

算法流程

1.初始化set，定义为dic
2.遍历，如果num在dic里，就返回重复的数字，否则就添加到dic内
3.返回-1

我的感悟

感觉这道题还有很多其它的解法，主要考察排序
排序的话还有二分法，堆排序等，可以回顾一下，可以会考时间复杂度和空间复杂度的问题
然后看到有更简单的解法

第二种方法

思想：
将索引和数字对应起来，一个索引对应一个数字，如果出现重复的指向就可以返回

Python 中， a, b = c, da,b=c,d 操作的原理是先暂存元组 (c, d)(c,d) ，然后 “按左右顺序” 赋值给 a 和 b

代码如下

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i=0
        while i<len(nums):
            if nums[i]==i:
                i=i+1
                continue
            if nums[nums[i]]==nums[i]:
                return nums[i]
            else:
                nums[nums[i]],nums[i]=nums[i],nums[nums[i]]
        return -1

时间复杂度：O（n）
空间复杂度：O（1）

两种方法对比

可以看出来第二种方法更省时省内存