找出數(shù)組中任意一個重復(fù)的數(shù)字！

• 思路1:把數(shù)組排序，從排序后的數(shù)組中找出重復(fù)的數(shù)字。但排序一個長度為n的數(shù)組需要O(nlogn)的時間。

• 思路2:利用哈希表。從頭到尾按順序掃描數(shù)組每個數(shù)字，每次掃描到一個數(shù)字的時候，都可以用O(1)的時間來判斷哈希表是否已經(jīng)包含了該數(shù)字，如果沒有就添加到表中，如果有就返回。這個算法時間復(fù)雜度是O(n)，但他提高時間的效率是以一個大小為O(n)的哈希表為代價的，以空間換時間。

• 思路3:如果數(shù)組中沒有重復(fù)的數(shù)字，那么當(dāng)數(shù)組排序后數(shù)字i將出現(xiàn)在下標(biāo)為i的位置?，F(xiàn)在我們重排這個數(shù)組，從頭到尾依次掃描每個數(shù)字，當(dāng)掃描到下標(biāo)為i的數(shù)字時，就先比較這個數(shù)字(用m表示)是不是等于i。如果是則繼續(xù)掃描，如果不是則拿它和第m個數(shù)字進行比較。如果相等，就找到了一個重復(fù)的數(shù)字，如果不相等，就把第i個數(shù)字和第m個數(shù)字交換，接下來再重復(fù)比較、交換的過程，直到發(fā)現(xiàn)重復(fù)的數(shù)字。
  代碼如下：

bool duplicate(int numbers[],int length,int* duplicate)
{
    if (numbers == nullptr || length <= 0)
    {
        return 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]])
            {
                *duplicate = numbers[i];
                return true;
            }
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return false;
}

上述代碼中不需要額外分配內(nèi)存，都是在原數(shù)組上進行的操作，空間復(fù)雜度為O(1)。代碼中有一個兩重循環(huán)，但每個數(shù)字最多只要交換兩次就能找到自己的位置，所以總的時間復(fù)雜度為O(n)。

現(xiàn)在我們將題目改變一下條件。

在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改數(shù)組本身。

• 思路1:由于不能修改原數(shù)組，我們可以新建一個輔助數(shù)組，然后逐一把原數(shù)組中的數(shù)字復(fù)制到輔助數(shù)組中。比如原數(shù)組中被復(fù)制的數(shù)字是m，那就把它復(fù)制到輔助數(shù)組下標(biāo)為m的位置。這樣很快就能找到哪個數(shù)字是重復(fù)的。需要O(n)的輔助空間。

• 思路2:為了避免空間開銷，我們討論一種更好的解決方法。采用類似二分查找的思想。把1～n的數(shù)字從中間數(shù)字m分成兩部分，前面一部分為1～m，后面一部分為m+1～n。如果1~m的數(shù)字中出現(xiàn)的次數(shù)大于m，則說明此區(qū)間一定有重復(fù)的數(shù)字。
  我們以數(shù)組{2,3,5,4,3,2,6,7}為例，根據(jù)題目要求，這個長度為8的數(shù)組中的所有數(shù)字都在1～7范圍內(nèi)。中間的數(shù)字4將1～7的范圍分成兩段，一段是1～4，一段是5～7，接下來我們統(tǒng)計1～4這4個數(shù)字在數(shù)組中出現(xiàn)的次數(shù)，它一共出現(xiàn)了5次，因此1～4中一定有重復(fù)的數(shù)字。接下來再把1～4的范圍一分為二，一段是1，2兩個數(shù)字，一段是3，4兩個數(shù)字。再統(tǒng)計后發(fā)現(xiàn)第3個和第4個在數(shù)組中一共出現(xiàn)了3次，這意味著這兩個數(shù)字中一定有一個重復(fù)了。我們分別再統(tǒng)計這兩個數(shù)字在數(shù)組中出現(xiàn)的次數(shù)。

代碼如下:

int getDuplication(const int* numbers,int length)
{
    if (numbers == nullptr || length < 0)
    {
        return -1;
    }
    int start = 1;
    int end = length - 1;
    while (end >= start)
    {
        int middle = (end - start) / 2;
        int count = countRange(numbers,length,start,middle);
        if (end == start)
        {
            if (count > 1)
            {
                return start;
            }
            else
            {
                break;
            }
        }

        if (count > (middle - start + 1))
        {
            end = middle;
        }
        else
        {
            start = middle + 1;
        }

    }
    return -1;
}
int countRange(const int* numbers,int length,int start,int end)
{
    if (numbers == nullptr)
    {
        return 0;
    }
    int count = 0;
    for (int i = 0;i < length; i++)
    {
        if (numbers[i] >= start && numbers[i] <= end)
        {
            ++count;
        }
    }
    return count;
}

注：需要指出的是，上述代碼并不能保證找出重復(fù)的數(shù)字。例如上述例子中的1～2的范圍里有1和2兩個數(shù)字，這個范圍的數(shù)字也出現(xiàn)里2次，但2是重復(fù)數(shù)字。

從上述分析中可以看出，如果面試官提不同的功能要求，那么我們最終選取的算法也將不同。