用锦标赛方法求出序列的第二大元素,并输出比较次数,算法c
时间: 2023-12-24 17:03:03 浏览: 25
锦标赛方法(Tournament Method)是一种求解序列中最大值或最小值的经典算法,它的时间复杂度为O(nlogn)。可以通过稍加修改,求出序列的第二大元素。
具体实现如下:
```c
#include <stdio.h>
#define MAXN 1000005
int tree[MAXN << 2], n;
int max(int a, int b) { return a > b ? a : b; }
int query(int l, int r, int rt) {
if (l == r) return tree[rt];
int mid = (l + r) >> 1;
int max_left = query(l, mid, rt << 1);
int max_right = query(mid + 1, r, rt << 1 | 1);
return max(max_left, max_right);
}
void build(int l, int r, int rt) {
if (l == r) {
scanf("%d", &tree[rt]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int main() {
scanf("%d", &n);
build(1, n, 1);
int max_num = query(1, n, 1), second_max_num = -1, cnt = 0;
for (int i = 1; i <= n << 1; i++) {
if (tree[i] < max_num && tree[i] > second_max_num) {
second_max_num = tree[i];
}
if (tree[i] == max_num || tree[i] == second_max_num) {
cnt++;
}
}
printf("第二大元素:%d\n比较次数:%d", second_max_num, cnt);
return 0;
}
```
算法思路:
首先用线段树求出序列中的最大值 $max\_num$,然后从线段树的根节点开始,遍历整个线段树,记录所有与 $max\_num$ 相等或者与之等于的元素,同时在遍历过程中找出最大的小于 $max\_num$ 的元素,即为序列的第二大元素。
最后输出第二大元素和比较次数即可。