首页 > 试题广场 >

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

[编程题]数组中出现次数超过一半的数字
  • 热度指数：878543 时间限制：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)
MSean头像 MSean
思路一：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等）
这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优；
参考代码如下： 
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
        // 因为用到了sort，时间复杂度O(NlogN)，并非最优
    	if(numbers.empty()) return 0;
        
        sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数
        int middle = numbers[numbers.size()/2];
        
        int count=0; // 出现次数
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i]==middle) ++count;
        }
        
        return (count>numbers.size()/2) ? middle :  0;
    }
};
思路二：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码如下： 
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
    	if(numbers.empty()) return 0;
        
        // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        int result = numbers[0]; 
        int times = 1; // 次数
        
        for(int i=1;i<numbers.size();++i)
        {
            if(times == 0)
            {
                // 更新result的值为当前元素，并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result)
            {
                ++times; // 相同则加1
            }
            else
            {
                --times; // 不同则减1                
            }
        }
        
        // 判断result是否符合条件，即出现次数大于数组长度的一半
        times = 0;
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i] == result) ++times;
        }
        
        return (times > numbers.size()/2) ? result : 0;
    }
};

编辑于 2016-08-23 16:04:29 回复(56)
Epiphany_now头像 Epiphany_now
题目限制条件 数字是小于等于 10000的   空间复杂度 O(1)
只需要创建一个长度为10000的数组a。遍历一遍目标数组，把目标数组每个数在a数组对应下标的数字加1，最后就得到了数字出现的次数，在遍历一遍数组a，找出大于  length/2的元素   
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int[] a=new int[10000];
        for(int i=0;i<array.length;i++){
            a[ array[i] ]+=1;
        }
        float num=array.length/2;
        for(int i=0;i<10000;i++){
            if(a[i] > num) return i;
        }
        return 0;
         
    }
}

发表于 2022-08-06 18:08:59 回复(0)
小文同学在努力头像 小文同学在努力 
function MoreThanHalfNum_Solution(numbers) {
  // write code here
  if (numbers.length === 1) return numbers[0];
  let map = new Map();
  for (let i = 0; i < numbers.length; i++) {
    if (map[numbers[i]]) {
      map[numbers[i]] += 1;
    } else {
      map[numbers[i]] = 1;
    }
  }
  for (let key in map) {
    if (map[key] > numbers.length / 2) return key;
  }
}
module.exports = {
  MoreThanHalfNum_Solution: MoreThanHalfNum_Solution,
};

发表于 2022-08-06 01:15:40 回复(0)
Java
望向路途头像 望向路途
题目给定明确数值大小，直接定义数组，下标为值，数值为数字的数量
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int l=array.length;
        int result=0;
        int[] res=new int[10001];
        for(int i:array){
            res[i]++;
            if(res[i]>(l/2)){
                result=i;
            }
        }
        return result;
    }
}

发表于 2022-07-08 09:01:50 回复(0)
Java
枉做好人头像 枉做好人 
    public int MoreThanHalfNum_Solution(int [] array) {
        //摩尔投票法
        int n = array.length;
        int count = 0;
        int res = -1;
        for (int i = 0; i < n; i++) {
            if (count == 0){
                res = array[i];
                count ++;
            }else if (array[i] != res){
                count--;
            }else if (array[i] == res){
                count ++;
            }
        }
        return res;
    }

发表于 2022-06-30 13:33:47 回复(0)
Python 3
曰无衣bupt头像 曰无衣bupt
一个一个的检查太麻烦了，而且对于大的数组时间复杂度更高。
直接借助set： 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        for i in set(numbers):
            if numbers.count(i)>len(numbers)/2:
                return i


发表于 2022-06-15 17:44:00 回复(0)
txy_钟琛头像 txy_钟琛 
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num: array) {
            if (map.containsKey(num)){
                int count = map.get(num);
                count++;
                if (count > array.length/2){
                    ans = num;
                    break;
                }
                map.put(num,count);
            }else {
                map.put(num,1);
            }
        }
        if (map.size() == 1){
            return array[0];
        }
        return ans;
    }
}

发表于 2022-05-27 11:51:03 回复(0)
Python 3
Vivimore头像 Vivimore

在保证一定有解的情况下，可以使用这种方法 时间复杂度O(n) 空间复杂度O(1)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        temp = -1
        cnt = 0
        for num in numbers:
            if cnt == 0:
                temp = num
                cnt += 1
            else:
                if num == temp:
                    cnt += 1
                else:
                    cnt -= 1
        return temp

哈希法
时间复杂度：O(n) 空间复杂度O(n)

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        n = len(numbers)
        mp = {}
        for num in numbers:
            if num not in mp:
                mp[num] = 1
            else:
                mp[num] += 1
            if mp[num] >= n / 2:
                return num
发表于 2022-05-18 21:47:51 回复(0)
C++
牛客嗷嗷头像 牛客嗷嗷 
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
    }
};

发表于 2022-03-30 18:03:12 回复(0)
C++
牛客730705474号头像 牛客730705474号 
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int count = 1;
        int cur = numbers[0];
        int pre = 0;
        for(int i = 1;i < numbers.size();i++){
            if(numbers[i]!=cur&&count==1){
                if(pre==numbers[i]){
                    cur = pre;
                    count++;
                }
                else{
                    pre = cur;
                    cur = numbers[i];
                }

            }
            else if(numbers[i]!=cur){
                count--;
            }
            else{
                count++;
            }
        }
        return cur;
    }
};

发表于 2022-02-25 16:18:29 回复(0)
Python 3
JaydenCheng头像 JaydenCheng 
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        half_len = len(numbers)/2
        num_dic = {}
        for i in numbers :
            num_dic[i] = num_dic.get(i, 0) + 1
            if num_dic[i] >= half_len :
                return i

发表于 2022-02-17 20:41:44 回复(0)
Python 3
长歌行abc头像 长歌行abc 
w=input()
w=w[1:-1]
w=list(map(int,w.split(",")))
l=len(w)/2 w=sorted(w)
d={} for i in w:
    d[i]=d.get(i,0)+1 w=list(set(w)) for i in w: if(d[i]>l): print(i)
发表于 2021-09-14 18:03:32 回复(0)
Java
together"头像 together"
遍历数组，同时用一个 Map<integer> 记录每个元素的出现次数，超过一半时直接返回即可。</integer>
<integer> 
import java.util.*;

public class Solution {

    // HashMap计数
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        // 处理数组长度只有1的特殊情况
        if (array.length == 1) {
            return array[0];
        }

        int threshold = array.length / 2;
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int num : array) {
            Integer cnt = cntMap.get(num);
            if (cnt == null) {
                cntMap.put(num, 1);
            } else if (cnt == threshold) {
                return num;
            } else {
                cntMap.put(num, cnt + 1);
            }
        }
        return -1;
    }
}

如果先对数组进行排序，那么出现次数超过一半的元素一定是数组的中位数，也就是排序后下标为n/2的那个元素（n为偶数时n/2是中间偏右的那个元素，n为奇数时n/2就是中间元素），所以我们的目标就是找到排序后下标为n/2的那个元素。这其实可以借助快速排序来实现：

快排的分区函数每次找到一个pivot放到数组的适当位置，将数组分为左右两个部分，左边元素都小于pivot，右边元素都大于pivot。此时如果pivot的下标i正好是n/2，那pivot就是出现次数超过一半的那个元素，返回它即可；如果i<n/2，那就对i的右半部分执行分区函数；如果i>n/2，那就对i的左半部分执行分区函数。总之最终一定能找到i==n/2的目标元素，《剑指Offer》给出的时间复杂度是O(n)。 

public class Solution {

    // 快速排序思想
    // 时间复杂度O(n)
    // 空间复杂度O(1)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int l = 0, r = array.length - 1;
        int target = array.length / 2;
        while (true) {
            int mid = partition(array, l, r);
            if (target == mid) {
                return array[target];
            } else if (target > mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }

    // 快排的分区函数
    public int partition(int[] array, int l, int r) {
        int i = l, j = r, pivot = array[l];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] < pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        return i;
    }
}

我们首先给出 Boyer-Moore 算法的详细步骤：

  • 维护一个候选众数candidate和它出现的次数count。初始时candidate为首元素，count为 0；

  • 我们遍历数组array中的所有元素，对于每个元素 x，进行如下判断：

    • 在判断 x 之前，如果count的值为 0，我们先将 x 的值赋予candidate，随后我们判断 x：

      • 如果 x 与candidate相等，那么计数器count的值增加 1；

      • 如果 x 与candidate不等，那么计数器count的值减少 1。

  • 在遍历完成后，candidate即为整个数组的众数。 

public class Solution {

    // 投票算法
    // 我个人觉得就是把本来对自己+1的票数，转化为对候选者的票数-1，这就等同于变相给自己投票了
    // 时间复杂度O(n)
    // 空间复杂度O(1)
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int candidate = array[0], cnt = 1;
        for (int i = 1; i < array.length; i++) {
            if (candidate == array[i]) { // 候选者票数+1
                cnt++;
            } else if (cnt > 0) { // 候选者票数-1, 相当于变相对array[i]的票数+1
                cnt--;
            } else { // 暂时没有候选者, 那就让array[i]作为候选者, 票数为1
                candidate = array[i];
                cnt = 1;
            }
        }

        return candidate;
    }

}


</integer>
发表于 2021-09-07 17:21:40 回复(0)
C++
恨别鸟惊心头像 恨别鸟惊心 
暴力循环...
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 1 || numbers.size() == 2){
            return numbers[0];
        }
        for(int i = 0; i < numbers.size(); i++){
            int c = 0;
            for(int j = 0; j < numbers.size(); j++){
                if(numbers[j] - numbers[i] == 0 && j != i)
                    c++;
            }
            if(c + 1 > numbers.size() / 2){
                return numbers[i];
            }
        }
        return 0;
    }
};

发表于 2021-08-29 23:44:24 回复(0)
Java
男神20190129221786头像 男神20190129221786 
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //摩尔投票
        int cnt = 0;
        int candidate = 0;
        for(int num : array){
            if(cnt == 0)
                candidate = num;
            cnt += candidate == num ? 1 : -1;
        }
        return candidate;
            
    }
}

发表于 2021-08-27 11:13:21 回复(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)
C++
riky头像 riky
摩尔投票法： 
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() <= 0) return 0;
        int ans = 0;
        int cnt = 0;
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(cnt == 0)
                ans = numbers[i], ++cnt;
            else{
                if(ans != numbers[i])
                    --cnt;
                else 
                    ++cnt;
            }
        }
        return ans;
    }
};


发表于 2021-08-21 16:18:27 回复(0)
Java
牛客慧头像 牛客慧 
//(借鉴)摩尔投票法
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int vote=0;
        int moreN=array[0];
        for(int i=0;i<array.length;i++){
            if(vote==0) moreN=array[i];
            if(array[i]==moreN){
                vote++;
            }else{
                vote--;
            }
        }
        return moreN;
    }
}

发表于 2021-08-18 21:12:33 回复(0)
C++
EriccCartman头像 EriccCartman
第三种方法真的牛逼。 
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int index = 0;
        int value = 0;
        for(int i = 0; i < numbers.size();i++){
            if(index==0) {
                value = numbers[i];
                index++;
            } else {
                if(value==numbers[i]) index++;
                else index--;
            }
        }
        return value;
    }


发表于 2021-08-13 18:26:35 回复(0)
Java
大厂绝缘体头像 大厂绝缘体 
public class Solution {
    //O(n)的时间  O(1)的空间
    public int MoreThanHalfNum_Solution(int [] array) {
        int val = 0;
        int count = 0;
        for(int x : array){
            if(count == 0){
                val = x;
                count++;
            }else{
                if(x == val) count++;
                else count--;
            }
        }
        return val;
    }
}
发表于 2021-08-10 20:25:04 回复(0)
提交观点

问题信息

数组 哈希
难度：
2319条回答 193352浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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