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

灰太狼 2023-02-18 01:44 17阅读 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;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

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

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

灰太狼/ 2023年02月18日 01:44/ 0 赞/ 18 阅读

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

> [剑指Offer 39 数组中出现次数超过一半的数字 \[easy\]][Offer 39 _ _easy] > ![在这里插入图片描述][watermark_type

小咪咪/ 2022年12月28日 00:59/ 0 赞/ 171 阅读

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

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 1.使用排序算法，将整个数组排序，然后中间的数字就是出现次数超过一半的数字。时间复杂度为O(nlogn)

- 日理万妓/ 2022年08月06日 00:12/ 0 赞/ 192 阅读

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

剑指offer面试题29~数组中出现次数超过一半的数字一.问题描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2

绝地灬酷狼/ 2022年06月17日 06:43/ 0 赞/ 210 阅读

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

一个数组中有一个数字的次数超过了数组的一半，求出这个字符。如：int a\[\]=\{2,3,2,2,2,2,2,5,4,1,2,3\}，求出超过一半的数字是2

太过爱你忘了你带给我的痛/ 2022年06月10日 22:55/ 0 赞/ 230 阅读

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

链接： [https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163][https_w

逃离我推掉我的手/ 2022年06月07日 02:25/ 0 赞/ 232 阅读

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

[数组中出现次数超过一半的数字][Link 1] 题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,

ゝ一世哀愁。/ 2022年03月25日 15:29/ 0 赞/ 218 阅读

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

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=12][

ゝ一纸荒年。/ 2022年03月20日 02:50/ 0 赞/ 221 阅读

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

时间限制：1秒空间限制：32768K 热度指数：281239 本题知识点：数组算法知识视频讲解题目描述数组中有一个数字出现的次数超过数组长度的一半，请

小咪咪/ 2022年03月09日 10:46/ 0 赞/ 239 阅读

相关【Java】数组中出现次数超过一半的数字

题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，

以你之姓@/ 2021年12月23日 23:31/ 0 赞/ 250 阅读