Amazon OA1 Coding 新题

bihuang0910 · 2015-12-26 04:24:22

yjtwm 发表于 2015-12-25 03:39
楼主，这题不是quick select吗？
直接套leetcode： Kth Largest Element in an Array
可以实现avg O（n） ...

前K个和第K个还是不一样吧？

yjtwm · 2015-12-26 04:45:16

bihuang0910 发表于 2015-12-26 04:24
前K个和第K个还是不一样吧？

不错，但你得到第k个以后再遍历一遍把小于k的拿出来也还是O（n），所以整体还是O（n）