題目連結：
題目大意：
給定一正整數 ｎ （０ ＜ ｎ ≦ １, ０００, ０００），代表有一數列有 ｎ 個數字。接著的 ｎ 列輸入即為此數列的內容。每列皆有一非負整數。
設此數列之數字分別為 Ｘ１ 、 Ｘ２ 、 …… 、 Ｘｎ ，請找到整數 Ａ 滿足
（｜Ｘ１ － Ａ｜ ＋ ｜Ｘ２ － Ａ｜ ＋ …… ＋ ｜Ｘｎ － Ａ｜）
為最小值。可能會有多組解，請輸出所有的可能。輸出格式請參考範例輸出。
範例輸入：
2
10
10
4
2
2
3
4
範例輸出：
A=10
A=2、3
解題思維：
可以看到可能的Ａ值基本上跟中位數有很大的關係，因為位於中間跟其他人的距離當然最近。
當然， ｎ 為奇數，也就是數列有奇數的元素時，Ａ即是中位數。但是當 ｎ 為偶數時， Ａ 值可以是數列中間兩個數之間的所有數字（數列中間是指由小到大排序後的中間），例如 １ 、 ２ 、 ５ 、 ７ ， Ａ 可以是 ２ ～ ５ 之間的任何數。
因此，我們的任務即是找到中位數。直接排序去找中間的元素固然可行，但是時間複雜度為 Ｏ（Ｎ × log Ｎ）。而這可以由快速選擇法（Quick Select）或是中位數的中位數（Median of Medians）以 Ｏ（Ｎ） 的時間複雜度達成。以下稍微介紹快速選擇法：
快速選擇法，其實跟快速排序法類似。從數列之中挑一個基準值（Pivot）去將數列分為「比基準值小」、「比基準值大」兩邊（等於的兩邊皆可放），然後判斷中位數位於哪一側（小的那邊還是大的那邊）並以相同方式去遞迴該側。幾層遞迴之後即可找到要的數字。
以上不只可以運用於尋找中位數，要找到數列第 Ｋ 大（小）的數字也是同理。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
