数组中出现超过一半的数字

绝地灬酷狼 2022-09-30 13:49 170阅读 0赞

题目1370：数组中出现次数超过一半的数字

时间限制：1 秒内存限制：32 兆特殊判题：否提交：3397解决：994  
题目描述：  
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。  
输入：  
每个测试案例包括2行：  
第一行输入一个整数n（1<=n<=100000），表示数组中元素的个数。  
第二行输入n个整数，表示数组中的每个元素，这n个整数的范围是\[1,1000000000\]。  
输出：  
对应每个测试案例，输出出现的次数超过数组长度的一半的数，如果没有输出-1。  
样例输入：  
9  
1 2 3 2 2 2 5 4 2  
样例输出：  
2  
思路分析

编程之美上有更详细的解法，为每个值设置一个“可信度”，当同一个数字连续重复出现时，可信度加1；遇到不同的数时，可信度减1；可信度减到0了就丢弃这个数，换成当前比较的元素。最后剩下的元素就是出现次数超过一半的那个。这样的话时间复杂度O(n)，空间复杂度O(1)。  
但是九度上需要进行判断元素是否出现超过一半，所以还是需要判断次数。我用map统计每个元素出现的次数。

#include <iostream>
    using namespace std;
    struct node{
        int num;
        int reliability;
    };
    int main(){
        int a[100];
        int n;
        node N;
        N.reliability = 1;
        cin >> n;
        cin >> a[0];
        N.num = a[0];
        for (int i = 1; i < n; i++){
            cin >> a[i];
            if (a[i] != N.num){
                N.reliability--;
                if (N.reliability == 0){
                    N.num = a[i];
                    N.reliability = 1;
                }
            }
            else{
                N.reliability++;
            }
        }
        cout << N.num;
        system("pause");
        return 0;
    }