首页 > 代码库 > 输出数组里面第N大的数
输出数组里面第N大的数
好像有些大公司出过面试题:找出数组里面第N大的数,当然有点变化,但本质部分是这样的.
要求是不能排序,时间复杂度不能超过O(n^2)
思路很多,我暂时就只会快排衍生的那种.如果对快速排序不太熟悉了,建议复习 我之前讨论的快速排序.
好的,现在假设你已经熟悉了快速排序.
每轮快排,我们都得找个支点,然后从数组的两边交替开始和支点比较,右边比支点小的数移到左边,左边比支点大的数移到右边,移到最后,只剩一个位置了,然后把支点填进来.这时,你发现在支点右边的数都比支点大.假设支点的index等于i,然后支点是第(endIndex-i+1)大的数了.(注意:endIndex是数组最后一个元素的下标)
记住我们的目标,我们的目标是要找第N大的数,如果endIndex -i + 1 = n,就说明我们找到了.但是2个数比较有3种结果.我们来分情况讨论下:
记th = endIndex - i + 1,find(a, startIndex, endIndex, n)
(1) th = n,返回支点
(2) th > n,说明第n大的数在支点右边,所以在右边继续找:find(a, i + 1, endIndex, n)
(3) th < n,说明第n大的数在支点左边,右边的数都比要找的数大,也比支点大,所以只需要在左边找第(n - th)大的数即可,find(a, startIndex, i - 1, n - th)
代码:
#include<stdio.h>#include<stdlib.h>int choose_nth(int a[],int startIndex, int endIndex, int n);int main(int argc, char *argv){ int a[] = {150,111,1000,99,300,10,189}; int n,i; int an = sizeof(a)/sizeof(int); printf("数组:\n"); for(i = 0 ; i < an; ++i) printf("%d ",a[i]); printf("\n"); printf("想找第几大的数:"); scanf("%d",&n); int ans = choose_nth(a, 0, an - 1, n); printf("第%d大的数是:%d\n", n, ans); return 0;}int choose_nth(int a[], int startIndex, int endIndex, int n){ int midOne = a[startIndex]; int i = startIndex, j = endIndex; if(i == j) //递归出口之一 return a[i]; if(i < j) { while(i < j) { for(; i < j; j--) if(a[j] < midOne) { a[i++] = a[j]; break; } for(; i < j; i++) if(a[i] > midOne) { a[j--] = a[i]; break; } } a[i] = midOne;//支点归位 int th = endIndex - i + 1;//计算下标为i的数第几大 if(th == n)//正好找到 { return a[i]; } else { if(th > n )//在支点右边找 return choose_nth(a, i + 1, endIndex, n); else//在支点左边找第(n-th)大,因为右边th个数都比支点大 return choose_nth(a, startIndex, i - 1, n - th); } } }
输出结果:
数组:150 111 1000 99 300 10 189 想找第几大的数:4第4大的数是:150
输出数组里面第N大的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。