剑指Offer_03_数组中重复的数字

题目描述：

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

示例：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：2 <= n <= 100000

解法1：修改数组

//代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)，另外，所有的操作步骤都是在输入数组上进行的，不需要额外分配内存，因此空间复杂度为O(1)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

        int temp;

        //我们注意到数组中的数字都在0～n-1的范围内，如果这个数组中没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字
        for (int i = 0;i < nums.size();i++) {

            while (nums[i] != i) {

                if (nums[i] == nums[nums[i]]) return nums[i];

                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }

        return -1;
    }
};

解法2：哈希表

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

        unordered_map<int, int> hash;  //定义一个哈希表

        for(int i = 0; i < nums.size(); ++i) {

            hash[nums[i]]++;  //遇到重复的数字，就将它的索引+1

            if (hash[nums[i]] != 1) return nums[i];
        }

        return -1;
    }
};