首页 > 试题广场 >

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

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

热度指数：862679 时间限制：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)

Java

牛客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

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号

// 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

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

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

方法一：采用众数与非众数的消除思路：如果两个数不相等，就消去这两个数，最坏情况下：每次消去一个众数和一个非众数，那么如果存在众数，后面留下的数肯定是众数，最后再接着在遍历一遍。代码如下：
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)

Java

做则必成的勇气和信心

import java.util.*;
 
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int n=array.length/2;
        int ans=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                int temp=map.get(array[i]);
                temp++;
                map.put(array[i],temp);
            }else{
                map.put(array[i],1);
            }
        }
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])>n){
                ans=array[i];
            }

        }
        return ans;
    }
}

发表于 2023-04-21 22:25:28 回复(0)

Java

dynamo1

摩尔投票算法
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length <= 0) {
            return -1;
        }
        int candidate = array[0];
        int vote = 1;
        for(int i = 0;i<array.length;i++) {
            if ( array[i] == candidate) {
                vote++;
            }else {
                vote--;
                if (vote == 0) {
                    candidate = array[i];
                    vote = 1;
                }
            }
        }
        return candidate;
    }
}

发表于 2023-04-11 21:54:44 回复(0)

Java

牛客827163596号

import java.util.*;

public class Solution {

public int MoreThanHalfNum_Solution(int [] array) {

Arrays.sort(array);

return array[array.length/2];

}

发表于 2023-03-30 16:59:00 回复(1)

Java

孤寡孤寡的亚瑟很细致

import java.util.HashMap;

import java.util.Map;

public class Solution {

public int MoreThanHalfNum_Solution(int [] array) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

int length = array.length;

if (length < 2) {

return array[0];

}

for (int i = 0; i < length; i++) {

if (map.containsKey(array[i])) {

Integer count = map.get(array[i]) + 1;

if (count > length / 2) {

return array[i];

} else {

map.put(array[i], count);

}

} else {

map.put(array[i], 1);

}

return 0;

}

发表于 2023-03-27 10:11:40 回复(0)

Java

随风567

import java.util.Arrays;

public class Solution {

public int MoreThanHalfNum_Solution(int [] array) {

    //排序

    Arrays.sort(array);

    return array[(0+array.length-1)/2];

}

}

发表于 2023-03-25 19:46:16 回复(0)

提交观点

问题信息

数组哈希

难度：

346条回答 2352收藏 187588浏览

通过挑战的用户

查看代码

小混子来啦

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

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

输入描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题