剑指Offer03 数组中重复的数字

键值一一对应，如果键存在重复返回键，没有就插入这个键

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        unordered_map map;           //unordered_map不排序，速度更快
        for(int num : nums) {                   //遍历数组
            if(map[num]) return num;            //map已经有了，就返回这个重复的数
            map[num] = true;                    //第一次出现就放在map里面
        }
        return -1;
    }
};

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

长度n的数组，数值范围为0~n-1。有重复的数字，数组元素的 索引 和 值 是 一对多 的关系。可以先将索引与值一一对应，多出的值就是重复的数。

     int findRepeatNumber(vector& nums){
         int i = 0;
         while(i 
Python 
若写为 nums[i], nums[nums[i]] = nums[nums[i]], nums[i],
 则 nums[i]会先被赋值，之后 nums[nums[i]] 指向的元素则会出错。
 
     def findRepeatNumber(self, nums: [int]) -> int:
         i = 0
         while i < len(nums):
             if nums[i] == i:
                 i += 1
                 continue
             if nums[i] == nums[nums[i]]: return nums[i]
             else: nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
         return -1