首页 > 试题广场 >

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

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

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

Javascript

牛客874244364号

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    numbers.sort()
    return numbers[Math.floor(numbers.length / 2)]
}

发表于 2022-09-14 21:48:45 回复(0)

Javascript

Xinleidebaby

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let map=new Map()
    let x=Math.floor(numbers.length/2)
    for(let i=0;i<numbers.length;i++){
        if(map.has(numbers[i])){
            map.set(numbers[i],map.get(numbers[i])+1)
            if(map.get(numbers[i])>x) return numbers[i]
        }else map.set(numbers[i],1)
    }
    return numbers[0]
}

发表于 2022-08-04 10:23:13 回复(0)

Javascript

怕浪猫

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let len = numbers.length
    let half = len >> 1
    let map = new Map()
    for(let i of numbers){
        if(map.has(i)) map.set(i, map.get(i)+1)
        else map.set(i,1)
        if(map.get(i) > half) return i
    }
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};

发表于 2022-05-29 10:05:52 回复(0)

Javascript

FoRtCurious

愁死我了 indexOf(n[i]) 写成了 indexOf(i) 还通过了五个测试用例，怼着判断条件找了半天

发表于 2021-12-12 10:59:40 回复(0)

Javascript

美英

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
        //解法一，统计
//     let target = numbers.length/2;
//     let n = '0';
//     let obj = {};
//     numbers.forEach(item=>{
//         if(obj[item]){
//             obj[item]++;
//         }else{
//             obj[item]=1;
//         }
//     })
//     for(let i in obj){
//         if(obj[i]>target){
//             n = i;
//         }
//     }
    //return n;
    //解法二，先排序，再取中间位置，向下取整
    numbers.sort((a,b)=>{
        return a-b;
    });
    return numbers[Math.floor(numbers.length/2)];
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};

编辑于 2021-11-16 19:51:24 回复(0)

Javascript

牛客65675554号

发表于 2021-11-15 10:05:49 回复(0)

Javascript

println()

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let map = new Map()
    for(let i=0;i<numbers.length;i++){
        if(map.has(numbers[i])){
            map.set(numbers[i],map.get(numbers[i])+1)
        }else{
            map.set(numbers[i],1)
        }
    }
    for(let item of map){
        if(item[1] > numbers.length / 2){
            return item[0]
        }
    }
}

发表于 2021-09-24 16:00:24 回复(0)

Javascript

思宋

JavaScript解法

function MoreThanHalfNum_Solution(numbers)
{
var data = {}
numbers.forEach((item)=>{
    if(data[item]){
        data[item]++
    }else{
    data[item]=1
    }
})
for(key in data){
if(data[key]>numbers.length/2){
return key
break
}
}
}

发表于 2021-09-16 23:27:11 回复(0)

Javascript

会飞得猿

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    var count = 0;
    var res = 0;
    for (var i = 0; i < numbers.length; i++) {
        if (count == 0) {
            res = numbers[i];
        }
        if (numbers[i] == res) {
            count++;
        } else {
            count--;
        }
    }
    console.log(res);
    return res;
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};

这是我的js代码，通过了。从头开始遍历，相等加1最后打印自减，若值至0，则进入上一步的判断，不至0，则进行下一步。

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    if (numbers.length == 1) {
        return numbers[numbers.length - 1];
    }
    // 排序
    numbers.sort();
    // 新建一个对象 将每个数出现的次数与此数组成键值对
    var obj = {}
    for (var i = 0; i < numbers.length; i++) {
        if (numbers[i] == numbers[i + 1] && numbers[i] != numbers[i - 1]) {//判断是否重复,是否已经放入容器
            var result = numbers[i];
            // console.log(result);
            var count = numbers.lastIndexOf(result) - numbers.indexOf(result) + 1;
            // console.log(count);
            // count 与 result组成键值对 做一个绑定
            obj[count] = result
            // console.log(obj[count]);
        }
    }
    // 此时对象中的key 是 count
    // 先获取到最大的key 与 numbers.length / 2 作比较 
    // 最终通过key获取value  这样就不会出现错乱了
    if (Math.max.apply(null, Object.keys(obj)) >= numbers.length / 2) {
        return obj[Math.max.apply(null, Object.keys(obj))];
    }
    else {
        return -1;
    }
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};

另一种方法，比较蠢，用了三个数组实现。其中所以为了保证每一个数出现的次数与这个数能够有一个绑定关系我用了一个对象将count与result做了绑定这样的话算出每个属性最大的key值与numbers.length / 2作比较大于等于的应该就是出现次数最多的那个key 再通过这个key找到value 就能正确匹配值了 .

发表于 2021-08-27 09:18:38 回复(0)

Javascript

夜寻极光。

 function pai(a,b){
        return a - b;
    }
    numbers.sort(pai);
    for(let i of numbers){
        if(numbers.lastIndexOf(i)-numbers.indexOf(i)+1>=numbers.length/2){
            return i;
        }
    }

发表于 2021-08-16 19:01:42 回复(0)

Javascript

牛客822067661号

function MoreThanHalfNum_Solution(numbers)
{
    function count(num){
        let len = numbers.filter(i => i === num);
        return len.length;
    }
    let set = Array.from(new Set(numbers));
    let find = set.find(i => count(i) > Math.floor(numbers.length/2))
    return find
}

发表于 2021-08-11 11:51:02 回复(0)

Javascript

牛客853870082号

两行搞完

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    numbers = numbers.sort((a,b) => a -b)
    return numbers[Math.floor(numbers.length/2)]
}
module.exports = {
    MoreThanHalfNum_Solution : MoreThanHalfNum_Solution
};

发表于 2021-07-28 00:19:15 回复(0)

JavaScript

王志晗

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    if(!numbers) return 0;
    let obj = {};
    for(let i=0;i<numbers.length;i++){
        if(obj[numbers[i]] && obj[numbers[i]].val == numbers[i]){
            obj[numbers[i]].count++;
        }else{
            obj[numbers[i]] = {
                val:numbers[i],
                count:1
            }
        }
    }
    let index = 0;
    for(key in obj){
        if(obj[key].count > numbers.length / 2){
            index = key;
        }
    }
    return index;
}

发表于 2021-04-19 16:06:13 回复(0)

JavaScript

油条包麻子

以前的查找出现最多次数字符串的老方法拿来改改，哈哈

function MoreThanHalfNum_Solution(numbers)
{
    const arr = numbers.join('').split('')
    const obj = {}
    let result = {}
    arr.forEach(e => {
        obj[e] = { key: e, count: obj[e] ? obj[e].count : 0  }
        if (Object.keys(obj).indexOf(e) > -1) {
            obj[e].count = !obj[e].count ? 1 : (obj[e].count + 1)
        } else {
            obj[e].count = 0
        }
    })
    const counts = Object.values(obj).map(e => e.count)
    const max = Math.max.call(null, ...counts)
    for (let i in obj) {
        if (obj[i].count === max) {
            result = obj[i]
        }
    }
        if (result.count > (arr.length / 2)) {
            return result.key
        } else{
            return 0
        }
}

发表于 2021-04-09 00:12:55 回复(0)

JavaScript

splwany

function MoreThanHalfNum_Solution(numbers)
{
    const myMap = {};
    const half = Math.floor(numbers.length / 2);
    for (const num of numbers) {
        num in myMap && myMap[num]++ || (myMap[num] = 1);
        if (myMap[num] > half) return num;
    }
    return 0;
}

发表于 2021-04-01 21:27:01 回复(0)

JavaScript

IPzzzi

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    //哈希表做法
    if(numbers.length == 1){
        return numbers[0];
    }else{
        var arr = Array(numbers.length).fill(0);
        for(var j = 0;j<numbers.length;j++){
            ++arr[numbers[j]];
        }
        for(var i = 0;i<arr.length;i++){
            if(arr[i] > (numbers.length / 2)){
                return i;
            }
        }
        return 0;
        }
}

编辑于 2021-03-17 19:26:35 回复(0)

JavaScript

略略97

JavaScript的10ms，没有借用map结构和函数，其实C++也可以这么写。

不过有人知道为什么明明代码通过了，却在自测输入那里一直显示内部错误吗？😪😪

function MoreThanHalfNum_Solution(numbers)
{
    const lang=numbers.length;
    if(numbers.length==0) return 0;
    else if(lang==1)return numbers[0];
    else if(lang==2)return (numbers[0]===numbers[1])?numbers[0]:0;
    var mid=Math.floor(lang/2);
    var temp=numbers[0],sum=1;
    for(let i=1;i<lang;i++){
        if(temp===numbers[i])
            sum++;
        else{
            sum--;
            if(sum<0){
                temp=numbers[i];
                sum=0;
            }
            continue;
        }
        if(sum>mid) return temp;
    }
    return (sum>0)?temp:0;
}

发表于 2021-01-20 14:29:38 回复(0)

JavaScript

别卷啦！

哈希map

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let l = numbers.length ,n = Math.floor(l/2)
    const map = new Map()
    for(let num of numbers){
        if(map[num]){
           map[num]++
           }else{
            map[num] = 1
           }
           if(map[num]>n) return num
        }    
        return 0
    }

发表于 2020-12-14 16:22:44 回复(0)

提交观点

问题信息

数组哈希

难度：

45条回答 2246收藏 185002浏览

通过挑战的用户

查看代码

小混子来啦

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

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

输入描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题