剑指3：数组中重复的数字

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    哈希表：unordered_map
*/
class Solution {
public:
    int duplicate(vector<int>& nums) {
        int length = nums.size();
        unordered_map<int, int> map;
        map.reserve(length);
        int repeatNum = -1; 
        
        for (int i = 0; i < length; i ++) {
            if (map.find(nums[i]) == map.end()) {
                map.insert({nums[i], 1});
            } else {
                repeatNum = nums[i];
                break;
            }
        }
        return repeatNum;
    }
};

/*
    集合：unordered_set
*/
class Solution {
public:
    int duplicate(vector<int>& nums) {
        int length = nums.size();
        unordered_set<int> set;
        int repeatNum = -1; 

        for (int num : nums) {
            if (!set.insert(num).second) {
                repeatNum = num;
                break;
            }
        }
        return repeatNum;
    }
};

/*
    不使用额外空间

    重排这个数组，从头到尾依次扫描这个数组的每个数字。
    当扫描到下标 i 的数字时，首先比较这个数字 x 是否等于 i。
        如果是，则接着扫描下一个元素；
        如果不是，则将它和第 x 个数字进行比较。如果它等于第 x 个数字，交换第 i 个数字和第 x 个数字。
*/
class Solution {
public:
    int duplicate(vector<int>& nums) {
        int length = nums.size();
        for (int i = 0; i < length; i ++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                swap(nums[i], nums[nums[i]]);
            }
        }
        return -1;
    }
};

C++ 代码 - leetcode

/*
    哈希表
*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int length = nums.size();
        unordered_map<int, int> map;
        map.reserve(length);
        int repeatNum = -1; 
        
        for (int i = 0; i < length; i ++) {
            if (map.find(nums[i]) == map.end()) {
                map.insert({nums[i], 1});
            } else {
                repeatNum = nums[i];
                break;
            }
        }
        return repeatNum;
    }
};

/*
    集合
*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int length = nums.size();
        unordered_set<int> set;
        int repeatNum = -1; 

        for (int num : nums) {
            if (!set.insert(num).second) {
                repeatNum = num;
                break;
            }
        }
        return repeatNum;
    }
};

/*
    原地置换，不使用额外空间
*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int length = nums.size();
        for (int i = 0; i < length; i ++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                swap(nums[i], nums[nums[i]]);
            }
        }
        return -1;
    }
};