第二大的数问题

描述
给出N个整数,请求出小于M的第二大的数。
输入
题目包含多组输入,每组数据第一行包括两个整数N,M（0<=M<=N<=1000),N,M=0时结束。第二行包括N个整数xi(0<=xi<=100000)。
输出
输出N个数中小于M的第二大的数,如果不存在则输出-1。
样例输入
5 103100 101 102 103 1045 103100 101 101 103 1040 0
样例输出
101101要代码

如果要简单的话，将所有数字用快速排序排好，然后用二分法找到小于M的第二大的数即可。时间代价是nlog(n) + log(n)

如果要高效的算法，则可以考虑使用最大堆，最大堆的好处是无需将所有数都排序。思路如下：

1。将输入时大于M的数都过滤，只留下小于M的数。

2。在小于M的数里，用最大堆的方法求出第二大的值。

建堆的算法时间为O(n),取第二大值的时间代价为log(n)，总代价为 O(n) + log(n).代码如下：

void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

bool IsLeaf(int n,int pos)
{
return (pos >= n/2) && pos < n;
}
void SiftDown(int* a, int n, int pos)
{
while( ! IsLeaf(n,pos))
{
int leftChild = 2* pos + 1;
int rightChild = leftChild + 1;

int maxChild = leftChild;
if(rightChild < n && a[rightChild] > a[leftChild])
maxChild = rightChild;

if( a[pos] < a[maxChild] )
{
swap(a[pos], a[maxChild]);
}

pos = maxChild;
}
}

void BuildHeap(int *a, int n)
{
for(int i = n/2 -1; i >=0; i --) SiftDown(a,n,i);
}

int main()
{

int n,m,count = 0;
scanf("%d %d",&n, &m);
int* a = new int[n];
for(int i = 0; i < n; i++)
{
scanf("%d",&a[count]);
if(a[count] < m) count++;
}

if( count < 2) printf("-1");

BuildHeap(a,count); //建立最大值堆
swap(a[0],a[count - 1]); //移除最大值, 将数组最后一个元素放到最大值的位置
SiftDown(a, count - 1, 0); //重新设置最大值

printf("%d",a[0]); ///输出此刻最大值
return 0;
}

能把样例给的详细点么？

我硬是没看懂你的样例