算法題：數組中重複的數字

找出數組中重複的數字：在一個長度為n的數組裡的所有數字都在0~n-1的範圍内。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是重複的數字2或者3。

審題：長度為n的數組，0~n-1的範圍，确定了肯定至少一個重複。注意是找出任意一個重複的數字即可。

思路：如果要排個序起手的話，就先要O(nlogn)的代價，然後再找。但是題目隻需要找到1個重複，那麼排序是有相當大的部分是浪費的。如果用哈希表呢？從頭掃到尾對這個數組，然後添加到表中，那麼第一個重複的值就很容易找到，似乎也沒有其他特别大的浪費空間。那麼代價就是O(n)，感覺提高了不少，但是還要一個大小為O(n)的哈希表為代價，總體來說劃得來。既然要另外空間，那麼有沒有不用輔助空間的呢？呀，好像給我的數組不就是一個空間嗎?原址搞起不是棒棒的？再看看題目，長度n，0~n-1範圍，那麼下标等于值？有搞頭！

做法：現在讓我們重排這個數組。從頭到尾一次掃描這個數組中的每個數字。當掃描到下标為i的數字時，首先比較這個數字（用m

表示）是不是等于i。如果是，則掃描下一個數字；如果不是，則再拿它和第m個數字進行比較。如果它和第m個數字相等，就找到

了一個重複的數字（該數字在下标為i和m的位置都出現了）；如果它和第m個數字不相等，就把第i個數字和第m個數字交換，把m

放到屬于它的位置。接下來再重複這個比較、交換的過程，直到我們發現一個重複的數字。

代碼：

 class Program

    {

        static void Main(string[] args)

        {

            int[] sample = { 5, 4, 2, 1, 3, 3 };

            int result = -1;

            Console.WriteLine(Duplicate(sample,sample.Length,ref result));

            Console.WriteLine(result);

            Console.ReadKey();

        }

        static bool Duplicate(int[] numbers, int length,ref int result)

        {

            if (numbers == null || 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]])

                    {

                        result = numbers[i];

                        return true;

                    }

                    int temp = numbers[i];

                    numbers[i] = numbers[temp];

                    numbers[temp] = temp;

                }

            }

            return false;

        }

    }

總結：注意到代碼中有個雙重循環，那麼是不是就以為這該算法起碼是O(n^2)呢？其實不然，因為每個數字最多隻要交換兩次

就能找到i,m相等的位置，是以總的複雜度還是O(n)，但原址交換，不需要輔助空間。

心得：這些問題其實就是寫那麼一個方法（不行就兩個）解決，傳進來的參數也是顯而易見的，重要的還是邏輯，細節就在于

把控傳入參數，魯棒性的檢測是必不可少的，是面試的加分項，邏輯通順還要缜密。開局八成就要來幾個if來檢驗下原始輸入

是否可行。然後才是邏輯核心。