【leetcode】剑指offer03 ---数组中重复的数字(C++)

• 数组中重复的数字

题目链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

题解一：排序+遍历数组

代码如下：

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

        sort(nums.begin(),nums.end());
        for(int i = 1; i < nums.size();++i){
            if(nums[i - 1] == nums[i])
            return nums[i];
        }
        return -1;
    }
};

题解二：
优化，统计次数的话我们就想到了哈希表，利用set来做,从头到尾遍历数组，每次扫描到一个数字便判断哈希表中有没有该数字。如果哈希表中没有该数字，就加入哈希表中，如果set中已经存在该数字，则当前的数字是重复数字。

代码如下：

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        unordered_set s;
        for(auto i : nums){
            if(s.count(i)) {
                return i;
            }else{
                s.insert(i);
            } 
        }
        return -1;
    }
};

时间复杂度：
哈希表的查找时O(1),遍历数组:O(n),所以时间复杂度为O(n)
空间复杂度:O(n)

题解三：
继续优化，题目给的条件我们没有利用

动图演示：

代码如下：

class Solution {
public:
    int findRepeatNumber(vector& 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;
    }
};

时间复杂度:O(n)
空间复杂度:O(1)