求教个第K大的数排序

bupttest

2019/3/2镜像同步28 回复

一个数组求第K的数，但是数组有重复的数，有啥好的处理方法，快排是不是就得做优化了

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

creaink机器人#1 · 2019/3/2

三路快排？

Biuuuuuuuu机器人#2 · 2019/3/2

改一下快排

Lss1995机器人#3 · 2019/3/2

第一步hash存储值->cnt，第二步对keys 进行partition，改改就好了。O(n)

hyforever机器人#4 · 2019/3/2

quick select?

Nroskill机器人#5 · 2019/3/2

经典的TopK问题方案一：快排改一下每次扔一半不管，只排有第K个数的那一半，扔到最后就剩第K个数了方案二：维护一个大小为K的最大堆或者大小为N-K+1的最小堆，每次都跟堆顶比，比如是最大堆的话，比堆顶大就扔掉，比堆顶小就把堆顶换了并且维护一下堆，保证堆始终是你当前遍历过的所有的数字中最小（大）的K（N-K+1)个数哪个快我不确定，反正肯定都比nlogn快，而且方案二更省内存

nianliunian机器人#6 · 2019/3/2

快排改一下，百度或者谷歌就有的，面试常见问题

Nroskill机器人#7 · 2019/3/2

没明白你这怎么就O(n)了…做partition是什么意思？【在 Lss1995 的大作中提到: 】 : 第一步hash存储值->cnt，第二步对keys 进行partition，改改就好了。O(n)

Azurill机器人#8 · 2019/3/2

quick select o(n)

bit3125机器人#9 · 2019/3/2

solution1：Tn=On Sn=O1(inplace) || On(!inplace) solution2：Tn=Onlogk Sn=Ok solution1具有更优的时间复杂度，但是有两个缺陷：想要达到常数级的空间消耗就必须inplace，不适合于不能修改数组而n又远大于k的场景(线性空间消耗)；2.必须针对静态的数据，无法面对大规模动态数据流的场景【在 Nroskill (Nroskill) 的大作中提到: 】 : 经典的TopK问题 : 方案一：快排改一下每次扔一半不管，只排有第K个数的那一半，扔到最后就剩第K个数了 : ...................