面试题3：数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

方法1：利用hash表特性，时间复杂度O(n),空间复杂度O(n)

思路：由于n个数字的范围已知，都在[0,n-1]之间，所以建立一个长度为n的数组hash，遍历输入数组，将hash数组中下标对应原数组数值的+1，所以hash数组的下标即为输入数组的值，hash数组的值即为对应下标表示的数的个数

#include<iostream>
#include<vector>
using namespace std;
/*
测试用例：空，只含一个数，没有重复，正常重复。
思路：因为数字范围是固定的[0,n-1],所以可以考虑哈希表
*/
bool duplicate(int numbers[], int length, int* duplication) {
    if (length <= 0 || numbers == NULL)
        return false;
    vector<int> hash(length,0);
    for (int i = 0; i < length; i++)
    {
        hash[numbers[i]]++;
    }
    for (int i = 0; i < length; i++)
    {
        if (hash[i] > 1)
        {
            *duplication = i;
            return true;
        }
    }
    return false;
}

int main()
{
    int numbers[] = {2,1,3,1,4};
    int length = sizeof(numbers) / sizeof(numbers[0]);
    int duplication;
    cout << duplicate(numbers, length, &duplication) << endl;
    cout << duplication << endl;
    return 0;
}

方法2：hash表改进,，时间复杂度O(n),空间复杂度O(n)

算法步骤：

开辟一个长度为n的vector<bool>, 初始化为false</bool>
遍历数组，第一次遇到的数据，对应置为true
如果再一次遇到已经置为true的数据，说明是重复的。返回即可。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
bool duplicate(int numbers[], int length, int* duplication) {
    if (length <= 0 || numbers == NULL)
        return false;
    vector<bool> hash(length,false);
    for (int i = 0; i < length; i++)
    {
        if (!hash[numbers[i]])
            hash[numbers[i]] = true;
        else
        {
            *duplication = numbers[i];
            return true;
        }        
    }
    return false;
}

int main()
{
    int numbers[] = {1,2,4,4,3};
    int length = sizeof(numbers) / sizeof(numbers[0]);
    int duplication=0;
    cout << duplicate(numbers, length, &duplication) << endl;
    cout << duplication << endl;
    return 0;
}

超级方法：时间复杂度O(n),空间复杂度O(1)

具体文字思路看书

#include<iostream>
#include<vector>
#include<map>
using namespace std;
bool duplicate(int numbers[], int length, int* duplication) {
    if (length <= 0 || numbers == NULL)
        return false;
    int i = 0, m = numbers[i];
    for (int i = 0; i < length; i++)
    {
        while (numbers[i]!=i)
        {
            if (numbers[i] == numbers[numbers[i]])
            {
                *duplication = numbers[i];
                return true;
            }
            swap(numbers[i], numbers[numbers[i]]);
        }
    }
    return false;
}

int main()
{
    int numbers[] = {1,2,4,4,3};
    int length = sizeof(numbers) / sizeof(numbers[0]);
    int duplication=0;
    cout << duplicate(numbers, length, &duplication) << endl;
    cout << duplication << endl;
    return 0;
}