Problem 10107 What is the Median?，中間數

Problem 10107 當你每輸入一個數，輸出到目前為止已輸入的數之中間數。

此題概念並不難，當輸入的數量為偶數，則取中間兩個數的平均和，例如：{1 ,4 ,5 ,8 ,9 ,29}中，數量為 6 ，6/2 = 3，也就是位置在3和4的數的平均和，(5+8)/2 = 6.5，則中間數為 6；而輸入的數量為奇數，則取排在中間的那一個數，例如：{1 ,4 , 6, 7, 9}，數量為 5， 5/2 = 2.5，也就是位置在 3 的數，則為中間數為6。

首先，題目有說他會輸入小於10000個數來測試，所以必須建立一個陣列來存放：

#define MAXLEN 10000
int Median[MAXLEN] ; 

每輸入一個值，就必須馬上存放：

if ( scanf("%d", &n) < 1) break;
Median[index] = n, index ++;

依照以上程式碼，可以看出每新增一個值，就會將它擺在目前陣列的最後一個位置。

接下來就可以將陣列排序了。一般來說，都會使用「氣泡排序法」來排序，但我可以告訴你：那是行不通的。因為「氣泡排序法」的效能為：若 n 個數要排序一次，需要 (n-1) + (n-2) + ... + 1 = n*(n-1)/2 次，效能非常之差，題目若真的有10000個數，則需要算上(n為1則0次、n為2則1次、...)...你們自己慢慢算...，絕對超過 3 秒。

既然我們知道每新增一個值就會將它擺在目前陣列的最後一個位置，只需要將最後一個索引值和它前一個索引值比較，如果小於前一個索引值，則交換其值；反之，則否。如此類推， n 個數要排序一次最多不過 n-1 次，比起「氣泡排序法」效能好太多了。

函式程式碼如下：

void Sort (int m[],int index) // index 為目前筆數
{
   int i, temp;
   for (i = index - 1; i >= 0 ; i --)
       if (m[i] < m[i - 1])
       {
           temp = m[i] ;
           m[i] = m[i - 1];
           m[i - 1] = temp;
       }   
}

用此方法，才用了 0.040 秒。

By David.k

p10107題目連結
回ACM題庫目錄
回首頁