At the cost of a hash table of size O(n), time O(n)

// Mark: Swift
class Solution {
    func findRepeatNumber(_ nums: [Int]) -> Int {
        var repeatNum = 0
        var numSet:Set<Int> = []
        for num in nums{
            if numSet.contains(num){
                return num
            }else{
                numSet.insert(num)
            }
        }
        return repeatNum
    }
}
Copy the code
//Mark: C++ class Solution { public: int findRepeatNumber(vector<int>& nums) { unordered_map<int,bool> dic; for (int &num: nums){ if (dic[num]) return num; dic[num] = true; } return -1; // unordered_map<int, bool> dic; // for (int &num: nums){if (dic[num]) return num; if (dic[num]) return num; // dic[num] = true; // } // return -1; }};Copy the code

Method 2: pigeon nest principle, because the element value < nums.size(); So we can place the element we see in the index, and repeat if the element already exists in the index when we swap. O (N) space is O (1)

Class Solution {public: int findRepeatNumber(vector<int> &nums) {// If (nums.empty()) {return 0; } for (int &num: nums){ if (num < 0 || num > nums.size()) { return 0; }} for (int I =0; i<nums.size(); ++i){ while(nums[i] ! = i){ if (nums[i] == nums[nums[i]]){ return nums[i]; } //swap int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } } return -1; }};Copy the code

Method 3: sort to see if the elements before and after are equal. O (NlogN) space is O (1)

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