PROBLEM

剑指 Offer 03. 数组中重复的数字

难度 简单

MY ANSWER

哈希表

使用哈希表来实现类似桶排序的方法。先查询表中有无该数，若有则返回，若无则放入表中。时间复杂度O(n)，空间复杂度O(n)。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); i++) {
            auto it = hashtable.find(nums[i]);
            if(it != hashtable.end()) {
                return nums[i];
            }
            else {
                hashtable[nums[i]] = 1;
            }
        }
        return 1;
    }
};

BETTER SOLUTION

原地交换

充分利用题目条件在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应。索引从0开始遍历，先判断索引与值是否相等，是则i++检查下一个索引，否则将当前索引的值与同值的索引的值进行交换，交换到索引与值相等为止。当前索引的值与同值的索引的值相等时，则说明找到了重复的数字，将其返回。时间复杂度O(n)，空间复杂度O(1)。

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

SUMMARY

用到了哈希表，没能做进一步的思考减少复杂度。牢记：题目给出的条件都是要派上用场的，充分利用好题目条件才能得到更优的答案，利用原地交换将值与索引对应，降低空间复杂度。