【在 p*****i 的大作中提到】 : 题目是: : How to find the kth largest element in an unsorted array of length n in O(n) : ?
w*z
12 楼
It's like the quick sort, pick the pivot. But to handle worst case for picking the pivot , you need to have the "median of median" thing.
you know about it.
【在 f*******n 的大作中提到】 : This is the famous linear-time selection algorithm. It is very : complicated. They won't expect you to tell exactly how it works; just that you know about it. : http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general : : n)
试试 int findKth(int* arr, int start, int end, int k, int last) { if (start == end) return start; int s1 = start; int e1 = end; int mid = arr[(e1+s1)/2];