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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 52. 数组中出现次数超过一半的数字原题链接中等

作者：

邓泽军 , 2019-03-15 11:14:09 , 所有人可见 , 阅读 6391

34

17

题目描述

如果一个数大于一半，这个数最后的数量肯定大于其他所有数的数量之和。

样例

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int count = 1, val = nums[0];
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i] == val) count++;
            else  count--;
            if (count == 0) 
            { 
                val = nums[i];
                count = 1;
            }

        }
        return val;
    }
};

19 评论

smz0118 9个月前

66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666

zhangs9 2023-08-02 11:15

# 我真的服了

wo怎么什么都不会 2022-02-27 16:38

天才啊

138smart 8个月前

牛

GyroZeppeli_5 8个月前

摩尔投票

panda_33 2023-06-09 17:40

牛皮

._8396 2023-03-14 14:30

你们写代码都不写输输入函数吗

WindSinging 2021-05-18 09:22

$x_a$

vincenyuan 2019-09-26 14:41

如果那个数字刚好是数组的一半，最后的count 为0，但是val是最后一个数，最后一个数可能不是我们要求的数，这样的话，返回的val是错的，比如1,1,1,2,3,4，最后到计算完4，count为0，val变为4，返回的就是4了

邓泽军 2019-10-11 11:12

题目说超过一半了，不存在刚好一半的情况

WakeUp 2019-11-07 15:41

最后再加一个判断，判断次数是否大于一半，不超过返回0

cnt = 0
for x in numbers:
    if x == val: cnt += 1
return val if 2*cnt > len(numbers) else 0

wt 2019-09-12 09:34

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

请问大神这种方式空间复杂度是$O(1)$么？