首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字
  • 热度指数：851056 时间限制：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)
提交观点

问题信息

数组 哈希
难度：
0条回答 185254浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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