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

原题链接：剑指 Offer 03. 数组中重复的数字

 

solution:

        哈希表存储出现过的数字,时间复杂度O(n)

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
       unordered_set<int> map;
       for(auto &x : nums) {
           if(map.count(x)) return x;
           map.insert(x);
       }
       return 0;         
    }
};

        排序+遍历，时间复杂度O(nlogn)

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

        给定元素一定在0~n - 1,如果出现次数都为1，一定可以交换到正确的位置。

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