3剑指OFFER之数组中重复的数字

参考资料：无

类似题目：

[1]华为第二次笔试题第二题
[2]50哈希表查找之第一个只出现一次的字符

自己之前的解答：

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        //如果数组为空
        if (numbers == nullptr)
            return false;
        //如果给定的数组不合格
        for(int i =0;i<length;i++)
        {
            if(numbers[i]<0 || numbers[i]>=length)
                return false;
        }
        //关键步骤
        //数组大小为255.必须初始化，这个我纠结了一下午啊
        int tmp[255]={0};    
        for(int i=0;i<length;i++)
        {
            tmp[numbers[i]]++;
        }
        
        for(int i=0;i<length;i++)
        {
            if(tmp[i]>1)
            {
                *duplication = i;
                return true;
            }             
        }
        return false;
        
    }
};

自己之前的解答（初级版）：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool FindDuplicatedNum(int nNum[], int nLen, int * pDuplicated)
{
    if (nNum == nullptr)
        return false;

    //sort(nNum,nNum+nLen);
    bool bFlag = false;
    for (int i = 0; i < nLen; i++)
    {
        for (int j = i + 1; j < nLen; j++)
        {
            if (nNum[i] == nNum[j])
            {
                *pDuplicated = nNum[i];
                bFlag = true;
                break;//break只会跳出里程那个循环
            }
        }
        if (bFlag == true)
            break;
    }

    if (bFlag == true)
        return true;
    else
        return false;
}




int main()
{
    int a[10] = {10,7,7,1,2,3,4,5,2,1};
    int nLen = sizeof(a) / sizeof(a[0]);
    int *pDuplicated=nullptr;
    pDuplicated = (int *)malloc(sizeof(int));
    cout << FindDuplicatedNum(a, nLen, pDuplicated);
    cout << *pDuplicated;
    system("pause");

}

自己之前的解答（改进版）：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool FindDuplicatedNum(int nNum[], int nLen, int * pDuplicated)
{
    if (nNum == nullptr)
        return false;
    for (int i = 0; i < nLen; i++)
    {
        if (nNum[i]<0 || nNum[i]>nLen)
            return false;
    }
    int nTmp[255] = { 0 };
    bool bFlag = false;
    for (int i = 0; i < nLen; i++)
    {
        nTmp[nNum[i]]++;
    }
    for (int i = 0; i < nLen; i++)
    {
        if (nTmp[nNum[i]] > 1)
        {
            *pDuplicated = nNum[i];
            bFlag = true;
            break;
        }
    }
    if (bFlag)
        return true;
    else
        return false;

}




int main()
{
    int a[10] = {10,7,7,1,2,3,4,5,2,1};
    int nLen = sizeof(a) / sizeof(a[0]);
    int *pDuplicated=nullptr;
    pDuplicated = (int *)malloc(sizeof(int));
    cout << FindDuplicatedNum(a, nLen, pDuplicated);
    cout << *pDuplicated;
    system("pause");

}