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