剑指Offer——数组中重复的数字

看到题目第一反应是：哈希
或者：排序，再依次遍历找到重复数字
或者：排序，如果第i个位置的数字不是i，一定存在重复

方法一：哈希

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> hashmap;
        for(int i:nums)
        {
            hashmap[i]++;
            if(hashmap[i]>1)
            {
                return i;
                break;
            }      
        }
        return -1;
    }
};

方法二：排序，遍历

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-1;i++)
        {
            if(nums[i]==nums[i+1])
            {
                return nums[i];
                break;
            }
        }
        return -1;
    }
};

方法三

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            while(i!=nums[i])
            {
                if(nums[i]==nums[nums[i]])
                {
                    return nums[i];
                    break;
                }
                swap(nums[i],nums[nums[i]]);
            }
        }
        return -1;
    }
};

第三个方法自己没有改出来，照着书上思路重新敲的，自己的代码没有考虑如果数组中的数字是{1，2，3，3}，即没有0的情况。
书中代码完美避开这个问题。

最后时间最少的是方法三。

越努力，越幸运！