Big Shot IT公司面試之謎

Question

上週我參加了幾家大型IT公司的面試。有一個問題讓我有點困惑。下面是使用（值問題的精確描述。（從採訪問題網站中的一個）

鑑於所述數據集，

A,B,A,C,A,B,A,D,A,B,A,C,A,B,A,E,A,B,A,C,A,B,A,D,A,B,A,C,A,B,A,F 

這可以減少到

(A; 16); (B; 8); (C; 4); (D; 2); (E; 1); (F; 1): 

，頻率）格式。

對於這些元組中的總共m個元組，以非特定順序存儲。設計一個返回數據集的第k階統計量的O（m）算法。 m是與n相對的元組的數量，它是數據集中元素的總數。

Answer 1

您可以使用Quick-Select來解決此問題。

天真：

1. 選擇一個元件從所述陣列
2. 把東西小於或等於所述樞軸在陣列的左側（稱爲樞軸），在右側的那些更大。
3. 如果主軸在位置k，那麼你就完成了。如果它大於k，則重複數組左側的算法。如果它小於k，則重複數組右側的算法。

有幾個細節：

1. 您需要可以挑選支點隨機（如果你很高興與預期O（M）爲代價），或使用確定性的中值算法。
2. 如果有很多值等於主鍵，則需要注意不要花費O（m^2）次。一個簡單的方法是做第二遍將數組拆分成3個部分而不是2個：小於數據透視的數據，等於數據透視的數據，以及大於數據透視的數據。