hey this question was discussed earlier rite???pls make use of Selection
algorithm...i think the worst case is O(n+logn).
http://en.wikipedia.org/wiki/Selection_algorithm
On Thu, Jul 22, 2010 at 9:53 PM, Tech Id wrote:
> Write an algo (in less than O(n^2)) to find k-th maximum in an
> unsor
make a min heap of first k elements and check if the next coming numbers and
update heap accordingly.
al last root of heap will give result.
O(nlogk-k(k-1)/2)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email t
You can use algorithim for finding median in unsorted array.
int medianofUnsortedArray(int a[], int low, int high, int rank){
int l, h, pivot;
int temp;
pivot = l = low;
h = high;
if(l<=h){
while(l a[pivot]) h--;
temp
use selection algorithm
On Thu, Jul 22, 2010 at 9:53 PM, Tech Id wrote:
> Write an algo (in less than O(n^2)) to find k-th maximum in an
> unsorted array of integers.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to t
From: Tech Id
> Subject: [algogeeks] find k-th maximum in an unsorted array
> To: "Algorithm Geeks"
> Date: Thursday, July 22, 2010, 8:53 PM
>
>
> Write an algo (in less than O(n^2)) to find k-th maximum in an
> unsorted array of integers.
>
> --
> You recei
you can sort them(in O(n log n)) then find it . this is O(nlog n)
or you can use "selection problem" ,by this you can solve it in O(n) ! look at
the chapter Medians and Order Statistics in CLRS book,,
--- On Thu, 7/22/10, Tech Id wrote:
From: Tech Id
Subject: [algogeeks] find k-
Write an algo (in less than O(n^2)) to find k-th maximum in an
unsorted array of integers.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send e
