logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
kth smallest element
avatar
kth smallest element# JobHunting - 待字闺中
l*h
1 楼
老题了，还是不知道怎么找？
Find kth smallest element from an unsorted array in linear time. worst case
complexity should be O(n+k)
where n is array size.
avatar
r*h
2 楼
先用partition找到前k大的k个元素，O(n)
再在前k大的里找最大的，O(k)
avatar
p*2
3 楼

worst case?

【在 r**h 的大作中提到】
: 先用partition找到前k大的k个元素，O(n)
: 再在前k大的里找最大的，O(k)
avatar
c*a
4 楼
quicksort partition 到k时，找左边最大，或者右边最小
avatar
m*P
5 楼
CLRS里面找
大概就是利用quick sort的patition方法
一个是平均o(n)
要做到worst case o(n) 需要找特别的pivot 大概就是median的median
不过要写出来 估计面试不需要吧

【在 l**h 的大作中提到】
: 老题了，还是不知道怎么找？
: Find kth smallest element from an unsorted array in linear time. worst case
: complexity should be O(n+k)
: where n is array size.
avatar
j*7
6 楼
Selection algorithm
相关阅读
微软这周末之前又要裁员了 (转载)给你们看看阿里的面试题有没有在迪斯尼干的兄弟姐妹面试题分享：把数字翻译成字符串难道不能跟HR提这种需求么？新搬来湾区，请教怎么能多认识些朋友？ (转载)Flatten Binary Tree to Linked List的recursive解法Uber在德国赢得重大胜利！我看PSDAU这几家公司好奇一问，关于PACKAGEcanon internship求内推Front End developers in NYC面试第一次遇到老印同公司同职位offer和平均工资不是一回事求靠谱ICC/CCCRefer: Groupon Getawaysgoogle也在大规模招聘码工中英语口语不好的多吗？DC地区全球性大公司cyber security researcher机会换工作TB test.
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。