首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字
  • 热度指数：878945 时间限制：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)
Java
allin秋招的秋田犬很苦闷头像 allin秋招的秋田犬很苦闷 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int candidate = numbers[0];
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (count == 0) {
                candidate = numbers[i];
                count++;
            } else {
                if (candidate == numbers[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return candidate;
    }
}

发表于 2025-10-16 22:46:56 回复(0)
Java
天天摸鱼的布莱恩很神奇头像 天天摸鱼的布莱恩很神奇
[1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024,1024
发表于 2025-04-22 10:39:36 回复(0)
Java
起床了的山羊很有一套头像 起床了的山羊很有一套
题目知识点有哈希，尝试用hashMap试了试

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        HashMap<Integer,Integer> a = new HashMap<Integer,Integer>();
        int half = numbers.length/2;
        for(Integer i:numbers){
            if(a.containsKey(i)){
                a.replace(i,a.get(i)+1);
            }else{
                a.put(i,1);
            }
        }
        for(Integer i:a.keySet()){
            if(a.get(i)>half)
                return i;
        }
        return -1;
    }
}
发表于 2025-04-21 14:48:02 回复(0)
Java
*.初见头像 *.初见 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        if (numbers == null || numbers.length == 0)
            return 0;
        if (numbers.length == 1) {
            return numbers[0];
        }
      

        int count;
        for (int i = 0; i < numbers.length; i++) {
            count = 0;
            for (int j = 0; j < numbers.length; j++) {
                if (numbers[i] == numbers[j]) {
                    count++;
                    if (count * 2 >= numbers.length)
                        return numbers[i];
                }
            }
        }
        return 0;
    }
}


发表于 2025-01-30 20:12:54 回复(0)
Java
牛客199615357号头像 牛客199615357号
public int MoreThanHalfNum_Solution (int[] numbers) {
        Arrays.sort(numbers);
        // write code here
        return numbers[numbers.length/2];
    }
发表于 2025-01-15 21:33:40 回复(0)
Java
牛客499848474号头像 牛客499848474号
用hashmap的🐷 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        if(numbers == null){
            return 0;
        }
        int n = numbers.length;
        int result = 0;
        HashMap<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(numbers[i])) {
                map.put(numbers[i], map.get(numbers[i]) + 1);
            } else {
                map.put(numbers[i], 1);
            }
        }
        for (int i = 0; i < n; i++) {
            if(map.get(numbers[i]) > n / 2){
                result = numbers[i];
                break;
            }
        }
        return result;
    }
}


发表于 2024-09-17 16:58:18 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here

        // 核心思想：创建哈希表统计对应元素的出现次数
        // 算法的实践复杂度O(N)，空间复杂度O(N)（空间复杂度为O(1)的方法暂时没有想出来）

        // 1.创建哈希表
        HashMap<Integer, Integer> hm = new HashMap<>();

        // 2.遍历数组，记录哈希表
        for (int cur : numbers) {
            if (hm.containsKey(cur)) {
                // 表中记录过当前key
                int count = hm.get(cur);
                count++;
                hm.put(cur, count);
            } else {
                // 表中没有及路过当前key
                hm.put(cur, 1);
            }
        }

        // 3.找到表中出现次数最高的那个key
        int max = 0;
        int result = numbers[0];
        // 3.1 将Map转化成Set，然后使用for遍历，方便使用外部的变量记录结果（匿名内部类不能使用外部变量记录）
        Set<Map.Entry<Integer, Integer>> entrySet = hm.entrySet();
        for (Map.Entry<Integer, Integer> entry : entrySet) {
            if (entry.getValue() > max) {
                max = entry.getValue();
                result = entry.getKey();
            }
        }

        return result;
    }
}

发表于 2024-09-03 14:33:07 回复(0)
Java
SUMMERENT头像 SUMMERENT 
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        for (int number : numbers) {
            map.put(number, map.getOrDefault(number, 0) + 1);
            if(map.get(number) > (numbers.length /2)){
                return number;
            }
        }
        return 0;
    }
}

发表于 2024-08-30 09:59:33 回复(0)
Java
牛客348570162号头像 牛客348570162号 
// hashmap
    public int MoreThanHalfNum_Solution1 (int[] numbers) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<numbers.length;i++){
            int v = 1;
            if(map.containsKey(numbers[i])){
                v = map.get(numbers[i]);
                map.replace(numbers[i],++v);
            }else{
                map.put(numbers[i],v);
            }
            if(v > numbers.length / 2){
                return numbers[i];
            }
        }
        return -1;
    }

    // 投票算法
    public int MoreThanHalfNum_Solution (int[] numbers) {
        int cond = -1,num = 0;
        for(int i=0;i<numbers.length;i++){
            if(num == 0){
                cond = numbers[i];
                num = 1;
            }else if(cond == numbers[i]){
                num++;
            }else{
                num--;
            }
        }
        return cond;
    }

发表于 2024-08-25 10:56:49 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        int res = numbers[0];
        int count = 1;
        for (int i = 1; i < numbers.length; i++) {
            if (count == 0) {
                res = numbers[i];
            }
            if (numbers[i] == res) {
                count++;
            } else {
                count--;
            }
        }
        return res;
    }
}

发表于 2024-08-12 10:50:39 回复(0)
Java
哈哈四渡赤水头像 哈哈四渡赤水
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
             // write code here
        HashMap<Integer,Integer> hashMap=new HashMap<>();

        for(int t=0;t<numbers.length;t++){
            hashMap.putIfAbsent(numbers[t], 0);
            hashMap.put(numbers[t], hashMap.get(numbers[t])+1);
            if(hashMap.get(numbers[t])>numbers.length/2)
                return numbers[t];
        }
        return -1;
    }
}
编辑于 2024-04-03 11:24:11 回复(0)
Java
十口先生头像 十口先生
public int MoreThanHalfNum_Solution (int[] numbers) {
        Arrays.sort(numbers);
        return numbers[numbers.length / 2];
}
发表于 2024-03-25 20:54:39 回复(0)
Java
hkcugwh头像 hkcugwh 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        Map<Integer, Integer> valueMap = new HashMap<>();
        int half = numbers.length / 2;
        for (int i = 0; i < numbers.length; i++) {
            int num = numbers[i];
            if (valueMap.containsKey(num)) {
                valueMap.put(num, valueMap.get(num) + 1);
            } else {
                valueMap.put(num, 1);
            }
            if (valueMap.get(num) > half) {
                return num;
            }
        }
        return 0;
    }
}

发表于 2023-11-30 15:13:10 回复(0)
Java
望三星头像 望三星 
public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        if (numbers.length == 1) return numbers[0];
        // 左右双指针，从两端找，如果两数不同则删去（置-1），相同则跳过
        int i = 0;
        int j = numbers.length - 1;
        int exist_count = numbers.length; // 统计剩余的非-1的数
        while (i < j) {
            if (exist_count <= 2) break;
            if (numbers[i] == numbers[j] || numbers[j] == -1) {
                j--;
            } else {
                numbers[i] = -1;
                numbers[j] = -1;
                exist_count -= 2; // 两数不同则抵消
                i++;
                j = numbers.length - 1; // 右端可能有非-1的其它数，所以将右指针重置
            }
        }
        for (int num : numbers) { // 最后剩下的数就是目标数
            if (num != -1) return num;
        }
        return -1;
    }
}

发表于 2023-09-12 22:01:27 回复(0)
Java
^ǒ^月亮船^头像 ^ǒ^月亮船^ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here

        if(numbers == null || numbers.length == 0){
            return 0;
        }
        Map<Integer,Integer> numMap = new HashMap<>();
        Integer key = 0;
        Integer max = 0;
        for(int i = 0; i < numbers.length ; i++){
            Integer val = numMap.get(numbers[i]);
            if(val == null){
                val = 1;
            }else{
                val = val + 1;
            }

            if(val > max){
                max = val;
                key = numbers[i];
            }
            numMap.put(numbers[i], val);
        }
        return key; 
    }
}

发表于 2023-08-28 19:38:11 回复(0)
Java
W_wwwww头像 W_wwwww
方法一：采用众数与非众数的消除思路：如果两个数不相等，就消去这两个数，最坏情况下：每次消去一个众数和一个非众数，那么如果存在众数，后面留下的数肯定是众数，最后再接着在遍历一遍。代码如下：
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution (int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int result = array[0];
        int len = array.length;
        int time = 1;
        for (int i = 1; i < len; i++) {
            if (time != 0) {
                if (array[i] == result) {
                    time++;
                } else {
                    time--;
                }
            } else {
                result = array[i];
                time++;
            }
        }
        int count = 0;
        for (int j = 0; j < len; j++) {
            if (result == array[j]) {
                count++;
            }
        }
        if (count > len / 2) {
            return result;
        }
        return 0;
    }
}

方法二：1、先对数组进行排序
               2、找到中间的数字X
               3、再次遍历这个数组，看X出现了多少次便可。代码如下：
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution (int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        Arrays.sort(array);
        int len = array.length;
        int midnum=array[len/2];
        int count = 0;
        for (int j = 0; j < len; j++) {
            if (midnum == array[j]) {
                count++;
            }
        }
        if (count > len / 2) {
            return midnum;
        }
        return 0;
    }
}
发表于 2023-07-30 02:45:01 回复(0)
Java
娜可璐璐头像 娜可璐璐
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        //转成数组进行遍历获取到每个字符
        for (int index = 0; index < numbers.length; index++) {
            //将获取到的值作为键
            //计数作为值
            int c = numbers[index];
            //判断集合中是否存在键
            if (m.containsKey(c)) {
                //如果存在，那么在值的后面加1
                m.put(c, m.get(c) + 1);
                //如果不存在那么就创建一个键值用于记录
            } else {
                m.put(c, 1);
            }
        }
        Set<Integer> s1 = m.keySet();
        int len = numbers.length/2;
        int num =0;
        for (int key : s1) {
            //通过集合遍历得到值
            int value = m.get(key);
            if (value > len) {
                num = key;
            }

        }
        return num;
    }
}
发表于 2023-07-06 19:43:33 回复(1)
Java
西橙先生头像 西橙先生 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int c = 0;
        int nums = numbers.length;
        int mid = 1;
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < nums;i++) {
            if (map.containsKey(numbers[i])) {
              int b = map.get(numbers[i]) + 1;
              if (b > mid) {
                mid = b;
              }
              if (nums/2 < mid) {
                    return numbers[i];
              }
              map.put(numbers[i],b);
            } else {
                map.put(numbers[i],1);
            }
        }
        return numbers[0];
    }
}

发表于 2023-06-24 18:02:37 回复(0)
Java
长白山啊头像 长白山啊 
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int nums =  array.length;
        if(nums == 1){
            return  array[0];
        }
        Map<Integer,Integer> map =new HashMap<>();
        for (int i = 0; i < nums ; i++) {
            if(map.containsKey(array[i])){
                map.put(array[i],map.get(array[i]) +1);
                if(map.get(array[i]) >=  nums/2 +1){
                    return  array[i];
                }
            }else{
                map.put(array[i],1);
            }
        }
        return -1;
    }
}

发表于 2023-05-23 14:25:05 回复(0)
提交观点

问题信息

数组 哈希
难度：
351条回答 193523浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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