N个数，求第K大数

本日同窗给我出了一道题是这样的：

有n个不一再的数，这n个数可以放入内存中，让你用最快的要领找到第k大的数。

解答：

一样平常环境我们也许思量，先将n个数排序（快排序、堆排序），然后可以获得功效。可是当n很大时这样做的服从会很低。以是我们提出一种更高效的要领：

操作快速排序的特点：第一遍排序会确定一个数的位置，这个数左边都比它大，右边都比他小（降序），当左边区间大于K时，声名我们求的第K大数在左边区间，这时我们可以舍弃右边区间，将范畴缩小到左边区间从而一再上述进程，直到确定一个数的位置时，左边区间的小是K-1那么这个数字就是我们所求。右边同理。

?

说明：可以或许行使这种要领的条件前提是：n个数不能一再。假如n个数中有一再，那么区间的巨细不能担保就是第K大。

譬喻：

444433221：个中3是第二大数，可是他的左边有4个数。

以是当标题酿成：有n个一再的数，求第K大数时，我们不能直接用上面的要领。

那么我们改怎么办理呢？

去掉一再！

去掉一再的要领有许多各人可以选择本身喜好的要领。我小我私人较量保举行使Hash。我们可以用HASH判重来将一再的数据去掉。然后再行使上述要领。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!