【剑指Offer】T39数组中出现次数超过一半的数字

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

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

思路 1:评论区看到的一种“投票算法”,即票数过一半者当选。

  • 设置票数 ticket 和 当选者 majority,遍历数组过程进行演变
    • A[i] 等于 majority,票数加 1
    • A[i]不等于 majority,票数减 1
    • 当票数为 0 时,更换当选者
  • 如果有到最后票数大于 1,那么当选者可能为要求的数字
    • 可以手动演变,只要数字大于总数的一半,最后当选者肯定会留下。
  • 再遍历一遍,统计数目,大于 len/2 即可认为符合要求,否则输出 0

代码:其中最后一个 for(int number : numbers){}可以当作foreach

int MoreThanHalfNum_Solution(vector<int> numbers) {
        int len = numbers.size();

        if(len == 0)
            return 0;

        int ticket = 1;
        int majority = numbers[0];

        for(int i = 1; i < len; i++){
            if(numbers[i] == majority)
                ticket++;
            else
                ticket--;

            if(ticket == 0){
                majority = numbers[i];
                ticket = 1;
            }
        }

        ticket = 0;
        for(int number : numbers){
            if(number == majority)
                ticket++;
        }

        return ticket > len / 2 ? majority : 0;
    }

思路 2:利用 Map,空间换时间。注意导入头文件

#include <map>
int MoreThanHalfNum_Solution(vector<int> numbers) {
    int n = numbers.size();
    map<int, int> m;
    int count;
    for(int i = 0; i < m; i++){
        count = m[number[i]]++;
        if(count > n/2)
            return number[i];
    }
    return 0;
}

本文链接:https://ariser.cn/index.php/archives/388/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!