首页 > 代码库 > 51 数组中重复的数字

51 数组中重复的数字

哈希

时间On 空间On

bool duplicate(int numbers[], int length, int* duplication) {    unordered_map<int, int> count;    for (int i = 0; i < length; i++)        count[numbers[i]]++;    unordered_map<int, int>::iterator ite = count.begin();    while (ite != count.end())    {        if (ite->second != 1)        {            *duplication = ite->first;            return true;        }        ite++;    }    return false;}

 

方法二

时间On空间O1

bool duplicate(int numbers[], int length, int* duplication){    if (numbers == NULL || length <= 0)        retrun false;    for (int i = 0; i < length; i++)    //根据题意检查数字合法性    {        if (numbers[i] < 0 || numbers[i] > length - 1)            return false;    }    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;}

 

51 数组中重复的数字