OJ题训练（三）

数组中重复的数字

题目来源

??牛客网：https://www.nowcoder.com/share/jump/8130885801691370918067

题目描述

??在一个长度为n的数组里的所有数字都在0到n-1的范围内。
数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
??例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
??数据范围：0≤n≤10000
??进阶：时间复杂度O(n) ，空间复杂度O(n)

题解

?方法一 ：暴力求解

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        for(int i = 0; i < numbers.size(); i++)
        {
            for(int j = i + 1; j < numbers.size(); j++)
            {
                if(numbers[i] == numbers[j])
                    return numbers[i];
            }
        }

        return -1;
    }
};

?方法二：位置重排

??数组长度为n，而取值范围是0 ~ n-1，假设没有重复值，那么就刚好每个位置的值和下标相对应。将每个值移动到对应下标的位置，当其他位置还有一个该下标的值时则必定是重复的。
假设数组numbers的值为{2,3,1,0,2,5,3}，第一个2和第二个2都会被移动到下标为2的位置上，但是在移动第二个2时，下标为2的位置上已经是2了，此时还有一个2，则表明，数字2是有重复的，就可以直接返回数字2。

class Solution {
public:
    int duplicate(vector<int>& numbers) {

        for(int i = 0; i < numbers.size(); i++)
        {
            // 如果位置本来就是对的，就跳过本次循环
            if(numbers[i] == i)
                continue;
            // 如果对应位置相等，则重复
            if(numbers[i] == numbers[numbers[i]])
            {
                return numbers[i];
            }
            // 将对应的值放到对应下标的位置
            int ret = numbers[numbers[i]];
            numbers[numbers[i]] = numbers[i];
            numbers[i] = ret;
        }

        return -1;
    }
};

?方法三：哈希表

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        // 哈希表记录重复
        unordered_map<int, int> mp;
        // 遍历数组
        for(int i = 0; i < numbers.size(); i++)
        {
            // 如果没有出现过就加入哈希表，否则就重复
            if(mp.find(numbers[i]) == mp.end())
                mp[numbers[i]]++;
            else
                return numbers[i];
        }

        return -1;
    }
};