首页 > 试题广场 >

在数组中找到出现次数大于一半的数

[编程题]在数组中找到出现次数大于一半的数
  • 热度指数:483 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整型数组arr,请打印其中出现次数大于一半的数,如果没有这样的数,请输出-1。
示例1

输入

[11,7,5,7,7]

输出

7
示例2

输入

[2,2,3,3]

输出

-1

备注:
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def findNum(self , arr ):
        # write code here
        dic = dict()
        for i in arr:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        maxx = max(zip(dic.values(), dic.keys()))
        if maxx[0] > len(arr) //2:
            return maxx[1]
        else:
            return -1

发表于 2021-10-21 21:09:27 回复(0)
不引入unordered_map的头文件会提示错误,头文件一般不是自动引入的吗?
#include<unordered_map>
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int findNum(vector<int>& arr) {
        // write code here
        unordered_map<int,int> map1;
        for(int val : arr)
        {
            map1[val]++;
            if(map1[val] > arr.size()/2)
            {
                return val;
            }
        }
        return -1;
    }
};
发表于 2020-09-11 11:12:07 回复(0)
若题目为一定存在次数超过一半的数字,找出该数字

那么问题为求解序列的中位数,可采取快速排序的思想,寻找中位数


另一种思路,若当前数字与之前相等,那么次数++
否则次数--
当次数为0时,换上新的数字
即:不同的一组数字 两两消去,剩下的即可能为超过一半的数字,在遍历一次,验证即可
复杂度: O(N)





  int findNum(vector<int>& arr) {
        // write code here
        int time=1;
        int result=arr[0];
        for(int i=0;i<arr.size();i++)
        {
            if(time==0)   //前面都已经消去
            {
                result=arr[i];
                time=1;
               
                
            }
            if(arr[i]==result)  //相等就累积上
            {
                time++;
            }
            else{             //不相等就成对消去
                time--;
            }   
        }
        
        int k=0;
        //最终剩下来的result即为 
        for(int i=0;i<arr.size();i++)
            if(arr[i]==result)
                k++;
        if(2*k>arr.size())
           return result;
        else
            return -1;
        

        
    }

发表于 2020-09-06 07:34:40 回复(0)