首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字
  • 热度指数：862810 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：，数组中元素的值
要求：空间复杂度：，时间复杂度

输入描述:
保证数组输入非空，且保证有解

示例1

输入

[1,2,3,2,2,2,5,4,2]

输出

2
示例2

输入

[3,3,3,3,2,2,2]

输出

3
示例3

输入

[1]

输出

1
算法知识视频讲解
添加回答
推荐
peter7788头像 peter7788
方法一：采用用户“分形叶”思路（注意到目标数 超过数组长度的一半，对数组同时去掉两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果），在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
            if(array==null||length<=0){
                return 0;
            }
            
            if(length==1){
                return array[1];
            }
            
            int[] tempArray=new int[length];
            for(int i=0;i<length;i++){
                tempArray[i]=array[i];
            }
            
            for(int i=0;i<length;i++){
                //后面需要用零来代表抹除数字，所以对0时做特殊处理
                if(tempArray[i]==0){
                    continue;
                }
                
                for(int j=i+1;j<length;j++){
                    if(tempArray[i]!=tempArray[j]&&tempArray[j]!=0){
                        tempArray[i]=0;//此处用0代表抹去该数字
                        tempArray[j]=0;
                        break;
                    }
                    
                }
            }
            
            for(int i=0;i<length;i++){
                System.out.println(tempArray[i]);
            }
            
            //找出未被抹去的数字
            int result=0;
            for(int i=0;i<length;i++){
                if(tempArray[i]!=0){
                    result=tempArray[i];
                    break;
                }
            }
            
            int times=0;
            for(int i=0;i<length;i++){
                if(result==array[i]){
                    
                    times++;
                }
            }
            
            if(times*2<length){
                result=0;
            }
            return result;
    }
}

方法二：剑指offer解法二（个人觉得与方法一基本就是同一个意思，异曲同工之妙）
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
        if(array==null||length<=0){
            return 0;
        }
        
        int result=array[0];
        int times=1;
        for(int i=1;i<length;i++){
            if(times==0){
                result=array[i];
                times=1;
            }else{
                if(array[i]==result){
                    times++;
                }else{
                    times--;
                }
            }
        }
        
        times=0;
        for(int i=0;i<length;i++){
            if(result==array[i]){
                times++;
            }
       }
            
       if(times*2<length){
           result=0;
       }
       return result;
    }
}
编辑于 2015-06-19 17:18:47 回复(111)
Python 3
在努力存钱的查理很甜美头像 在努力存钱的查理很甜美
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#
# import re

class Solution:
    def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
        # write code here
        a = str(numbers)
        numbers.sort()
        b = 0
        c = []
        print(numbers)
        if len(numbers)<=1:
            return numbers[0]
        for i in numbers:
            if i not in c:
                c = []
                c.append(i)
            elif i in c and len(c)>=len(numbers)/2:
                return c[0]
                break
            c.append(i)
           
           
               
           












发表于 2023-03-24 02:08:30 回复(0)
Python 3
秋叶红霜CCCCCC头像 秋叶红霜CCCCCC 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        count = 0
        candidate = None
        for i in numbers:
            if count == 0: # 票为0，先换候选人
                candidate = i
            count += 1 if i == candidate else -1 # 投给候选人，则票数+1，头给别人，票数-1
        return candidate

发表于 2022-11-06 11:47:49 回复(0)
Python 3
蓝鲸与风头像 蓝鲸与风 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        d=dict()
        for num in numbers:
            if not d.get(num):
            #target-numbers[i-1],则放入哈希表中
                d[num]=1
            else:
                d[num]+=1
        d1=sorted(d.items(),key=lambda x:x[1])
        return d1[-1][0]

发表于 2022-08-20 15:08:24 回复(0)
Python 3
牛客96188058号头像 牛客96188058号
两行代码搞定，解题思路：有重复数字超过数组长度的一半，那么排序后，数字中间的数字必定是该数字。 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        numbers.sort()
        return numbers[len(numbers)//2]


发表于 2022-07-18 18:44:06 回复(0)
Python 3
YiMo_以沫头像 YiMo_以沫
1. 排序之后最中间的数一定是出现超过一半的数字。时间复杂度O(NlogN)，不稳定。 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        return sorted(numbers)[len(numbers) >> 1]
2. 找众数，题目保证有解，所以众数一定是出现超过一半的数字。
先预设众数preNum和出现的次数count。
遍历数组，若count == 0，说明现在还没有众数，保存在preNum中并将count置为1。
若count > 0，则表示现在有众数，判断当前的数是否等于预设的众数，如等于将count + 1，若不等于则将count - 1.
注意最后count中并不是众数出现的次数。 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        preNum, count = 0, 0
        for i in numbers:
            if count:
                count = count + 1 if preNum == i else count - 1
            else:
                preNum, count = i, 1
        return preNum



发表于 2022-06-21 10:26:06 回复(0)
Python 3
来牛客玩玩头像 来牛客玩玩 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        if len(numbers) == 1:
            return numbers[0]
        for x in set(numbers):
            if numbers.count(x) > len(numbers)//2:
                return x

发表于 2022-06-20 22:48:56 回复(0)
Python 3
曰无衣bupt头像 曰无衣bupt
一个一个的检查太麻烦了，而且对于大的数组时间复杂度更高。
直接借助set： 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)/2:
                return i


发表于 2022-06-15 17:44:00 回复(0)
Python 3
牛客647218893号头像 牛客647218893号 
def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        has = {}
        res = []

        for i in range(len(numbers)):
            if numbers[i] in has:
                has[numbers[i]] += 1
            else:
                has[numbers[i]] = 1
            if has[numbers[i]] > int(len(numbers)/2):
                res = numbers[i]
        return res

发表于 2022-06-13 16:34:19 回复(0)
Python 3
东方佑头像 东方佑 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)//2:
                return i
发表于 2022-06-08 18:22:25 回复(0)
Python 3
Vivimore头像 Vivimore

在保证一定有解的情况下，可以使用这种方法 时间复杂度O(n) 空间复杂度O(1)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        temp = -1
        cnt = 0
        for num in numbers:
            if cnt == 0:
                temp = num
                cnt += 1
            else:
                if num == temp:
                    cnt += 1
                else:
                    cnt -= 1
        return temp

哈希法
时间复杂度：O(n) 空间复杂度O(n)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        n = len(numbers)
        mp = {}
        for num in numbers:
            if num not in mp:
                mp[num] = 1
            else:
                mp[num] += 1
            if mp[num] >= n / 2:
                return num
发表于 2022-05-18 21:47:51 回复(0)
Python 3
哦啦啦啊哦哦头像 哦啦啦啊哦哦 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        rating=0
        for num in numbers:
            if rating==0:
                res=num 
            if num == res:
                rating +=1
            else:
                rating -=1
        return res
        # 直观的话就是哈希表记录每个字符出现的次数 但是时间空间复杂度都是O(n)
        # 用摩尔投票 就会让空间复杂度变O(1)
        # 因为这道题肯定是出现次数最多的为解 
        # 但是简单说的话就是先设置第一个是m 票数设为1 后面是m的就+1 不是m就-1 
        # 直到票数变为0 重新设一个m 票数也重新记为1
        # 原理不懂 但是试一试确实是这样

发表于 2022-05-06 16:31:12 回复(0)
Python 3
牛客394879911号头像 牛客394879911号
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        len1=len(numbers)/2
        dict1=dict()
        for i in numbers:
            if i not in dict1:
                dict1[i]=1
            else:
                dict1[i]+=1
        for k,v in dict1.items():
            if v>=len1:
                return k
            
发表于 2022-04-29 09:57:32 回复(0)
Python 3
danspace头像 danspace 
from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        d = Counter(numbers)
        return d.most_common(1)[0][0]


发表于 2022-04-19 14:58:28 回复(0)
Python 3
想搞机器学习的小白头像 想搞机器学习的小白
摩尔投票 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        #投票
        count = 0
        for num in numbers:
            if count==0:half = num
            if num==half:
                count+=1
            else:count-=1
        return half


发表于 2022-04-12 16:07:26 回复(0)
Python 3
路痴喵头像 路痴喵
请问python使用内置函数遍历后超时，有没有什么解决方法呀？比如下面这样： 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in numbers:
            if numbers.count(i) > len(numbers)//2:
                return i


发表于 2022-03-21 23:03:16 回复(0)
Python 3
付付吖头像 付付吖
mid=len(numbers)//2
        d={}
        for i in numbers:
            if i not in d:
                d[i]=1
            else:
                d[i]+=1
        for i in d:
            if d[i]>mid:
                return i
发表于 2022-03-14 19:57:04 回复(0)
提交观点

问题信息

数组 哈希
难度：
36条回答 187637浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号