How to find the missing integer in an array.

題目的詳細條件是,未排序的n個連續整數中少了一個,要找出是哪一個,例如:3, 6, 9, 7, 8, 4,連續整數範圍為3-9,少了5。

說明

這個題目我們直覺得可以使用Hashtable的方式來判斷哪些數字出現過,但是這樣題目就太簡單了,所以一般會再有一個額外的限制:空間複雜度為O(1)。

所以在不使用Hashtable的情況下,我們只能用數學的方式去求解,此等差數列正好為梯形公式:(上底 + 下底) * 高 / 2。

接著利用公式的理論總和減去實際總和就是缺少的數字,以上面的例子為例:

(3 + 9) * 7 / 2 = 42
3 + 6 + 9 + 7 + 8 + 4 = 37
42 - 37 = 5

解法

使用C#

        static int Find(int[] array)
        {
            int max = array[0];
            int min = array[0];
            int sum = 0;
            for (int i = 0; i < array.Length; ++i)
            {
                int n = array[i];
                max = Math.Max(n, max);
                min = Math.Min(n, min);
                sum += n;
            }
            return (max + min) * (max - min + 1) / 2 - sum;
        }
文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()