查找第k小的元素(O(n)递归解法)
今天分享一个小技巧，虽然是小技巧但是还是很有价值的，曾经是微软的面试题。题目是这样的，一个无序的数组让你找出第k小的元素，我当时看到这道题的时候也像很多人一样都是按普通的思维，先排序在去第K个，但是当数组非常大的时候，效率不高，那有没有简单的方法了，其实我们早就学过，只是我们不善于思考和变通。很多人刚开始非常热衷于各种排序算法只是了解却没深究，这个题目的复杂度是O(n)，原理就是快速排序里面的划分算法。
分析：快速排序选择一个pivot对数组进行划分，左边小于pivot，右边大于等于pivot，所以我们计算左边小于pivot(加上pivot)的个数count总共有多少，如果等于k,正是我们所要的，如果大于k，说明第k小的数在左边，那就在左边进行我们的递归；否则，在右边，那么说明右边的第k-count小的数就是我们所要的，在右边进行我们的递归。
代码如下：
1 #include"stdio.h"
2 int GetMinK(int A[],int n,int k)
3 {
4 int s=-1,i=0,j=n-1,temp;
5 int beg=i;
6 int end=j;
7 while(s!=k)
8 {
9 beg=i;
10 end=j;
11 temp=A[i];
12 while(i<j)
13 {
14 while(i<j&&A[j]>=temp)j--;A[i]=A[j];
15 while(i<j&&A[i]<=temp)i++;A[j]=A[i];
16 }
17 A[i]=temp;
18 s=i;
19
20
21 if(s==k)
22 return A[k];
23 if(s>k){i=beg;j--;} //在左侧寻找
24 if(s<k){j=end;i++;} //在右侧寻找
25 }
26 }
27 int main()
28 {
29 int A[]={2,3,4,1,5,10,9,7,8,6};
30 int k=3;
31 printf("第%d小元素为：(从0开始)\n%d ",k,GetMinK(A,10,k));
32 return 0;
33 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读