performance - 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 个这样的元组，没有特定的顺序存储。设计一个 O(m) 算法，返回数据集的第 k 阶统计量。 m 是元组的数量，n 是数据集中元素的总数。

Answer 1

您可以使用 Quick-Select来解决这个问题。

天真地:

1. 从数组中选择一个元素(称为枢轴)
2. 将小于或等于枢轴的东西放在数组的左边，大于的放在右边。
3. 如果枢轴位于位置 k，那么你就完成了。如果它大于 k，则在数组的左侧重复该算法。如果小于k，则在数组右侧重复算法。

有几个细节:

1. 您需要随机选择基准(如果您对预期的 O(m) 作为成本感到满意)，或者使用确定性中值算法。
2. 如果有很多值等于主元，您需要注意不要花费 O(m^2) 时间。一种简单的方法是进行第二次传递，将数组分成 3 个部分而不是 2 个部分:小于主元的部分、等于主元的部分和大于主元的部分。