数组中出现次数超过一半的数字-蒲公英云

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

灰太狼 2023-02-18 01:44 116阅读 0赞

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

遍历一次数组，两两删去不同的数字，剩下的数字为可能值，还要遍历一次数组确实这个可能值出现的次数。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int size = numbers.size();
        if (size == 0) return 0;
        stack<int> s;
        for(int i = 0; i < size; i++) {
            if(s.empty()) s.push(numbers[i]);
            else if (s.top() != numbers[i]){
                s.pop();
            }else {
                s.push(numbers[i]);
            }
        }
        if(s.empty()) return 0;
        else {
    int num = s.top();
        int count = 0;
        for(int i = 0; i < size; i++) {
            if(num == numbers[i]) count++;
        }
        if( count > size/2) return num;
        else return 0;}
    }
};

大佬的代码：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        //map 记录出现次数
        map<int, int> m;
        int count;
        for (int i = 0; i < n; i++) {
            count = ++m[numbers[i]];
            if (count > n/2) return numbers[i];
        }
        return 0;
    }
};