Question: You are given an array of N integers. Your job is to find maximum and second maximum element in N+logN comparisons.
Solution: #include
typedef struct
{
unsigned a;
unsigned b;
}Max2ndMax;
Max2ndMax findMaxN2ndMax(int a[], int i, int j)
{
Max2ndMax ret;
int n = j - i;
if(n == 0)
{
ret.a = ret.b = a[i];
return ret;
}
else if(n == 1)
{
if(a[i] > a[j])
ret.a = a[i], ret.b = a[j];
else
ret.a = a[j], ret.b = a[i];
return ret;
}
int mid = (i + j)/2;
Max2ndMax ret1 = findMaxN2ndMax(a, i, mid);
Max2ndMax ret2 = findMaxN2ndMax(a, mid + 1, j);
if(ret1.a > ret2.a)
{
ret.a = ret1.a;
ret.b = ret2.a > ret1.b ? ret2.a : ret1.b != ret1.a ? ret1.b : ret2.a;
}
else
{
ret.a = ret2.a;
ret.b = ret1.a > ret2.b ? ret1.a : ret2.b != ret2.a ? ret2.b : ret1.a;
}
return ret;
}
int main()
{
int n;
scanf("%d", &n);
int a[n];
int i;
for(i = 0; i < n; ++i)
scanf("%d", a + i);
Max2ndMax m = findMaxN2ndMax(a, 0, n-1);
printf("Max = %d\t 2ndMax = %d\n", m.a, m.b);
}