首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字

热度指数：848842 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围： $n \le 50000$ ，数组中元素的值 $0 \le val \le 10000$

要求：空间复杂度： $O(1)$ ，时间复杂度 $O(n)$

输入描述:

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

示例1

输入

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

输出

示例2

输入

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

输出

示例3

输入

[1]

输出

算法知识视频讲解

推荐

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)

一个优雅的程序猿

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    int HashTable[10000]={0}, i;
    for(i=0; i<numbersLen; i++) 
        HashTable[numbers[i]]++;
    
    for(i=0; i<sizeof(HashTable); i++) {
        if(HashTable[i] > numbersLen/2)
            return i;
    }
    return -1;
}

编辑于 2024-03-20 18:00:48 回复(0)

牛客944385736号

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    //太慢了，换个思路，第一种方法是用相同数组下标记录每个数字出现的次数
    // if (numbersLen==0) {
    //     return -1;
    // }else if (numbersLen==1) {
    //     return numbers[0];
    // }
    // int count=1;
    // int arr[numbersLen];
    // for (int i=0; i<numbersLen; i++) {
    //     count=1;
    //     for (int j=0; j<numbersLen; j++) {
    //         if (numbers[i]==numbers[j]&&i!=j) {
    //             count++;
    //         }
    //         arr[i]=count;
    //         if (arr[i]>numbersLen/2) {
    //             return numbers[i];
    //         }
    //     }
    // }
    
    // return -1;
    //第二种方法是用源数组的数字作为下标，记录每个数字出现的次数
    int count[10001];
    for (int i=0; i<numbersLen; i++) {
        count[numbers[i]]++;
    }
    for (int i=0; i<sizeof(count)/sizeof(count[0]); i++) {
        if (count[i]>numbersLen/2) {
            return i;
        }
    }
    return -1;

}

编辑于 2024-03-12 14:02:57 回复(0)

陈让然

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) 
{
    // write code here
    //数组为空
    if(!numbers)
    {
        return -1;;
    }
    //开空间存储元素个数
    int*count=calloc(1001,sizeof(int));
    //遍历每个元素并计数
    for(int i=0;i<numbersLen;i++)
    {
        count[numbers[i]]++;
        //超过一半直接输出
        if(count[numbers[i]]>(numbersLen)/2)
        {
            return numbers[i];
        }
    }
    //没有超过一半
    return -1;
}

发表于 2023-11-21 20:41:30 回复(1)

帅奶哟。

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    int count[10001];
    int i, j;

    for (i = 0; i < numbersLen; i++){
        count[numbers[i]]++;
    }
    for (i = 0; i < 10001; i++){
        if (count[i] > numbersLen/2) {
            return i;
        }
    }
    return 0;
}

发表于 2023-03-17 19:03:09 回复(0)

木弎

//别的不对说暴力求解
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    int input=0;//计数器
    int i=0;
    for(i=0;i<numbersLen;i++)
    {
        int j=0;
        for(j=0,input=0;j<numbersLen;j++)
        {
            if(numbers[j]==numbers[i])//判断某元素的出现次数，出现计数器加一
            {
                input++;//计数器加一
                 if(input>(numbersLen/2))//判断某元素出现的次数是否超越了数组的一半
                {
                    return numbers[i];
                }
            }
        }
       
    }
    return 0;
}

发表于 2022-11-25 09:04:30 回复(1)

lmghzzq

符合题目要求的解法
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here              //这个方法参考2013年408考研的代码题的最优解法
    int count=0,a=numbers[0];     //a用于记录可能是出现超过一半的数组，出现一次count+1，不是则+1
    for(int i=1;i<numbersLen;i++){
        if(numbers[i]==a) count++;    //如果这个数是可能数a，则count+1
        else{
            if(count>0) count--;    //若这个数不是，则判断count，count>0则表明a还是有可能是的
            else{
                a=numbers[i];        //否则的话替换掉，因为目标数出现超过一半，所以最终还是会替换回来的
                count=1;
            }
        }
    }
    return a;
}

发表于 2022-10-07 18:58:05 回复(2)

回应我吧爱莉希雅

/**
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int MoreThanHalfNum_Solution(int* A, int numbersLen ) {
    // write code here
    int i = 0,j = numbersLen-1;
    while(i<j){
        if(A[i]==A[j])
            i++,j--;
        else{
            A[i]=A[j]=-1;
            i++,j--;
        }
    }
    for(i=0;i<numbersLen&&A[i]==-1;i++);
    int c = A[i];
    int cnt=0;
    for(i=0;i<numbersLen;i++)
        if(A[i]==c) cnt++;
    return c;
    //居然过了？虽然肯定有缺陷就是了 测试用例覆盖的不是很全啊
}

发表于 2022-09-25 20:28:52 回复(0)

try～～

/**
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    unsigned int cntarray[10000] = {0};//可能会栈溢出:与值的最大有关
    unsigned int cnt = 0;
    unsigned int val = 0;
    unsigned int div =numbersLen/2;
    if((numbers==NULL)||(numbersLen<0)){//参数安全检测
        return -1;
    }
    while(cnt<numbersLen){
        if(++cntarray[numbers[cnt]]>div){
            return numbers[cnt];
        }
        cnt++;
    }
    return -1;
}

发表于 2022-07-29 21:23:25 回复(0)

牛客918717262号

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
// write code here
int* array=(int*)malloc(sizeof(int)*10000);
for(int i=0;i<numbersLen;i++){
int m=numbers[i];
array[m]++;
if(array[m]>(numbersLen/2)){
return m;
}
}
return 0;

}

//不知道哪儿错了，8/11组用例通过

发表于 2022-04-02 16:35:01 回复(1)

笑笑风格

1、摩尔投票法

/**
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    int votes=0;
    int start=numbers[0];
    
    for(int i=0;i<numbersLen;i++)
    {
        if(start!=numbers[i])
        {
            votes--;
            if(votes==0)
            {
                start = numbers[i];
                votes++;
            }
        }
        else
        {
            votes++;
        }
    }
    return start;
}

发表于 2022-01-18 19:26:53 回复(1)

CreatorSY

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    int *all = calloc(sizeof(int), 10001);

    for (int i = 0; i < numbersLen; i++)
        all[numbers[i]]++;
    for (int i = 0; i < 10001; i++)
        if (all[i] > numbersLen / 2)
            return i;

    return 0;
}

发表于 2022-01-06 22:52:31 回复(0)

海饼干666

#define max 10000
int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) {
    // write code here
    int ret =0;
    if(numbersLen==1) {
        ret=numbers[0];
        return(ret);
    }
    int tab[max]={};
    for(int i=0;i<numbersLen;i++)
    {
        tab[numbers[i]]++;
    }
    for(int i=0;i<=max;i++)
    {
        if(tab[i]>numbersLen/2) return(i);
    }
    return 0;
}

发表于 2021-08-06 17:11:07 回复(0)

牛客972306957号

int MoreThanHalfNum_Solution(int* numbers, int numbersLen )
{
/* 参考官方题解候选法 */
int outValue = numbers[0];
int outNum = 1;
for (int i=1;i<numbersLen;i++)
{
if (outNum == 0) outValue=numbers[i];
if (outValue==numbers[i])
{
outNum++;
}
else
{
outNum--;
}
}
return outValue;

}

/* 不知道这个数组为什么时间会超

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

编辑于 2021-07-25 12:24:08 回复(0)

提交观点

问题信息

数组哈希

难度：

16条回答 2246收藏 185007浏览

通过挑战的用户

查看代码

小混子来啦

2022-11-23 17:44:57
imdante...

2022-11-11 19:55:11
Anthon523

2022-11-10 10:48:07
牛客89418...

2022-10-26 10:48:42
牛客54041...

2022-10-16 14:46:56

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

输入描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题