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个：小于数据透视的数据，等于数据透视的数据，以及大于数据透视的数据。