注册 登录
编程论坛 → 数据结构与算法

[求助]英雄树，用c语言实现

it明少 发布于 2016-04-20 08:52， 3012 次点击
Description

有n个数字，其中有一个数字的出现次数超过总个数的一半，这个数称之为英雄数。
例如，n=12，整数序列5，5，5，5，5，5，1，2，3，4，5，6，其中的英雄数为5。

对于给定的n个整数组成的序列，请使用数据结构堆栈，设计出一个时间复杂度为O(n)算法，计算出序列中的英雄数。

Input

由键盘提供输入数据。文件的第1行有1个正整数n<=1000000，表示整数序列有n个整数。第2行是整数序列，整数大小都在32位有符号整型内，数字之间以一个空格隔开。
输入数据保证必然存在一个数字，其出现次数超过总个数的一半。

Output

程序运行结束时，将指定序列的英雄数输出到屏幕上。

Sample Input


12
5 5 5 5 5 5 1 2 3 4 5 6

Sample Output


5

Source
2 回复
#2
it明少2016-04-20 08:52
#3
azzbcc2016-04-21 11:01
大致思路是这样。

程序代码：
#include <ext/hash_map>
#include <iostream>
#include <stdint.h>

using namespace std;
using namespace __gnu_cxx;

int main(int argc, char *argv[])
{
    int tmp, n;
    hash_map<int, int> map;

    cin >> n;
    for (int i = 0;i != n;i++)
    {
        cin >> tmp;
        map[tmp]++;
    }
    hash_map<int, int>::const_iterator iter;
    for (iter = map.begin();iter != map.end();++iter)
    {
        if (iter->second > n / 2)
        {
            cout << iter->first << endl;
        }
    }
    return 0;
}
1
©2025, BCCN.NET
电脑版