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

[编程题]在数组中找到出现次数大于一半的数

热度指数：483 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整型数组arr，请打印其中出现次数大于一半的数，如果没有这样的数，请输出-1。

示例1

输入

[11,7,5,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)

C/C++

牛客83754369号

不引入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)