{讨论}{算法}{线性时间选择}线性时间选择的变种问题

[fihopzz]

给定一个每个元素都不同的数组，找第k小或者k大都可以在线性的时间内得到。
如果数组中有重复的数：比如：
2 3 4 5 2 2 2 3.
现在如果是找第3小，要求给出结果4
是否存在线性时间的解法？
大家有没有思路，先谢了啊。

PS:
一种可能的思路：
（1）先将这个数组变成互异的数组，上例中：2 3 4 5
（2）然后找第三小。
问题变成是否存在一种线性的解法，将一个数组变成互异数组。
在上例中，似乎很简单：开个以最大元素为长度的数组即可。但是如果数组中的数字特别大，这个方法显然不优。

[fihopzz]

貌似可以通过hash来去掉数组中的重复元素。

[浩]

通过随机选择+快速排序的思想，
最后貌似只能说运行时间的期望值是O(n)（即E(T(n))=O(n))

[fang yuhao]

hash去重复元素

 

然后用线性的方法来找第k个元素。

[Cheng, Long]

做一个k大小的最大（最小）堆，然后遍历数组往堆里插即可，超出k之后将最小
（最大）元素扔掉。时间复杂度是O(nlgk)

fihopzz 写道:

[raymond]

如果单纯使用数组会碰到数据稀疏，空间效率不高的问题。可以使用二进制保存结果，对于二进制来说，1和1000000占用的空间是一样的，但是需要额外
的数据结果来操作，会产生side effect，具体结果如何需要实验验证。

On 11月19日, 上午5时38分, fihopzz <xiao...@gmail.com> wrote:

[liuxinyu]

这一结论可以参考CLRS中9.2：最坏结果是O(n^2)，只是期望值是O(n)。
前面建议Hash的方法，如果数据稀疏就不妙了。我想到的也只有K最大（小）堆了。

[Justin Turner]

第一感觉hash的空间省不了。

http://www.cnblogs.com/drizzlecrj/archive/2009/08/23/1537910.html

其中的解法4、解法6、解法7均可以扩展为题目中的情况。

解法4： 要在二分结果后，判断的时候用hash去重计数

解法6： 构建大小为k的堆时，在更新堆的时候用hash检查是否与堆内元素互异

解法7： 每一个hash中元素的个数都算1

[denny]

可看算法导论一书中的'计数排序'方法.

On 11月19日, 上午5时38分, fihopzz <xiao...@gmail.com> wrote:

[Haibo Huang]

如果数据集中，Counting Sort线性排序即可。
否则恐怕只能hash判重。这个就和hash函数的好坏相关了。如果不想浪费hash空间，也可以用一些带平衡的二叉树判重，如TreeSet。用这种
方法可以顺便找到第K大：每次插入一个元素后如果元素数为K+1则把最大一个删除即可。
判重后找第K大的方法就比较多了。比如二分第K大的值，然后线性扫描数比它大的数的个数。或者用堆维护前K。

On 11月19日, 上午5时38分, fihopzz <xiao...@gmail.com> wrote: