重复输入的快速选择算法？

Question

我已经熟悉了 quickselect 和 median-of-medians 用于快速 selection 未排序数组中的第 k 个元素。如果你足够努力，你可以保证最坏情况下的时间复杂度在 O(n) 之内。

我的问题有点不同。我想 select 来自未排序数组的第 k 个数字，该数组包含大量不可预测的重复项。我想知道的是，相对于输入的总大小 n，是否有一种方法在唯一值的数量 u 方面既节省内存又节省时间。问题是有时 u << n 有时 u ~ n。（实际上，u 几乎不变，而 n 波动很大。）

错误方法 1（请原谅我的 python 伪代码，问题与 python 具体无关）：

input = ...
k = ...

m = hashmap()
for value in input:
    if value exists in m:
        m[value] = m[value] + 1
    else:
        m[value] = 1

cumulative_sum = 0
for unique_value in ordered(m):
    cumulative_sum += m[unique_value]
    if cumulative_sum > k:
        return unique_value

这是我目前的基准。我不喜欢的是使用比较排序或保持 m 排序需要 O(u*logu) 时间。

错误方法 2：

input = ...
k = ...

M = some_value
assert type(input) == integral
assert min(input) == 0
assert max(input) == M

a = array(size=M+1, default_value=0)

for value in input:
    m[value] = m[value] + 1

cumulative_sum = 0
for i in range(M+1):
    cumulative_sum += m[i]
    if cumulative_sum > k:
        return i

这显然很糟糕，因为它需要 O(M) 时间和 O(M) space。

有没有什么好的方法可以快速更新select（或者干脆干点别的）在O(u)时间和O(u)space解决问题？

正如@kcsquared 指出的那样，如果输入数组按原样给出，则无法打破 Omega(n) 时间限制。如果输入的格式为 [(v1, c1), (v2, c2), ..., (vn, cn)]，是否有任何变化，其中 (v, c) 对应于一个唯一值； v 是值，c 是它在原始输入中出现的次数？

Answer 1

为了记忆，是的。

创建哈希映射值以进行计数。此散列的大小为 O(u)。然后你可以做一个快速选择，给每个值一个等于计数的权重。

但是为了时间，你必须读取整个数组 O(n)。除非您对近似答案感到满意。在这种情况下，您可以从数组中随机选择，计算出近似计数的散列，然后快速选择它。根据目的，这可能足够接近了。

重复输入的快速选择算法？

Fast selection algorithm for duplicate-heavy inputs?

algorithm

duplicates

top-n