找出所缺的整數

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

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 -->

小殘的程式光廊