An optimised approach to find the second largest number in an array.
There can be various solutions to this problem. I've listed three solutions which I found from the internet.
Solution 1:
int main()
{
unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
int size = sizeof(arr)/sizeof(unsigned char);
int i=0;
unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
for(i=0;i<size;i++)
{
if(arr[i]>max)
{
sec = max;
max=arr[i];
}
else if(arr[i]>sec && arr[i]!=max)
{
sec = arr[i];
}
}
printf("max = %d\nsec = %d",max,sec);
return 0;
}
This solution has a time complexity of ~O(n)
Solution 2:
To sort the array using the fastest algorithm viz. QuickSort: O(nLogn) and get the second largest.
The time of this technique O(nLogn) is still slower than O(n) therefore Solution 1 is preferable.
Solution 3:
In this technique the array is broken in groups of two and selection and elimination is done like a knock out tournament.
This technique has a time complexity of O(n + logn - 2)
Reference: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-number-of-comparisons/3628777#3628777
My Solution:
int main()
{
unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
int size = sizeof(arr)/sizeof(unsigned char);
int i=0,j=0;
unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
for(i=1;i<=size;i+=2)
{
j=(arr[i-1]>arr[i]);
if(arr[i-j]>max)
{
sec = max;
max=arr[i-j];
}
else if(arr[i-j]>sec && arr[i-j]<max)
{
sec = arr[i-j];
}
}
printf("max = %d\nsec = %d",max,sec);
return 0;
}
This technique shows a time complexity of ~O(n/2)
Please correct me, if we have a difference in opinion.
Thanks Ajitav :)
There can be various solutions to this problem. I've listed three solutions which I found from the internet.
Solution 1:
int main()
{
unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
int size = sizeof(arr)/sizeof(unsigned char);
int i=0;
unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
for(i=0;i<size;i++)
{
if(arr[i]>max)
{
sec = max;
max=arr[i];
}
else if(arr[i]>sec && arr[i]!=max)
{
sec = arr[i];
}
}
printf("max = %d\nsec = %d",max,sec);
return 0;
}
This solution has a time complexity of ~O(n)
Solution 2:
To sort the array using the fastest algorithm viz. QuickSort: O(nLogn) and get the second largest.
The time of this technique O(nLogn) is still slower than O(n) therefore Solution 1 is preferable.
Solution 3:
In this technique the array is broken in groups of two and selection and elimination is done like a knock out tournament.
This technique has a time complexity of O(n + logn - 2)
Reference: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-number-of-comparisons/3628777#3628777
My Solution:
int main()
{
unsigned char arr[] = {13,10,2,1,5,9,7,6,19,14,13,15,19};
int size = sizeof(arr)/sizeof(unsigned char);
int i=0,j=0;
unsigned char max = 0, sec = 0;//sec is used for the second largest no. in the array
for(i=1;i<=size;i+=2)
{
j=(arr[i-1]>arr[i]);
if(arr[i-j]>max)
{
sec = max;
max=arr[i-j];
}
else if(arr[i-j]>sec && arr[i-j]<max)
{
sec = arr[i-j];
}
}
printf("max = %d\nsec = %d",max,sec);
return 0;
}
This technique shows a time complexity of ~O(n/2)
Please correct me, if we have a difference in opinion.
Thanks Ajitav :)
