First declare a global int array max[k], where max[0] will contain maximum
of the array, max[1] will contain second max and so on. Now initialize the
all max array elements by some negetive number, assuming that the negative
number does not occur in the array or whatever with you can initialize that
array as what we do in traditional searching an element in an array. There
are two cases,
a) If the max[0] element changes, then we have to do one left the entire
max array upto kth position of the max element. My idea is if one max
element value changes to some value, its old value will be the max which was
below to it.
b) If max[0] does not changes, we have to check which max value becomes
lower to current array element. Accordingly, we have to do left shift, as
stated above.
I have attached my code also. Have a look at it. Its O(n*k)
On 22 July 2010 23:20, Azadeh Mousavi <[email protected]> wrote:
> 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 <[email protected]>* wrote:
>
>
> From: Tech Id <[email protected]>
> Subject: [algogeeks] find k-th maximum in an unsorted array
> To: "Algorithm Geeks" <[email protected]>
> 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 received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to
> [email protected]<http://mc/[email protected]>
> .
> To unsubscribe from this group, send email to algogeeks+
> [email protected]<http://mc/[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
regards,
soumya prasad ukil
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include<stdio.h>
void find_max(int [],int,int);
int max[15];
main()
{
int a[]={4,1,2,3,6,5,12,34,56,90,10,7,26,19};
int i,k=5;
for(i=0;i<k;i++)
max[i]=-1;
find_max(a,14,k);
printf("%dth MAX: %d\n",k,max[k-1]);
}
void find_max(int a[],int n,int k)
{
int i,j,flag=1,p,l=1;
for(i=0;i<n;i++)
{
if(max[0]<a[i])
{
for(j=0;j<k-1;j++)
max[k-j-1]=max[k-j-2];
max[0]=a[i];
}
else
{
for(j=0;j<k-1;j++)
if(a[j]!=a[j+1])
{
flag=0;
break;
}
if(flag)
{
for(j=1;j<k;j++)
max[j]=a[i];
}
else
{
for(j=1;j<k;j++)
{
if(max[j]<a[i])
{
l=1;
for(p=j;p<k-1;p++)
{
max[k-l]=max[k-l-1];
l++;
}
max[j]=a[i];
break;
}
}
}
}
}
}
