我要招人

去企业版

首页 > 试题广场 >

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

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

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

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

输入描述:

输入包含两行，第一行包含一个整数n，代表数组长度，第二行包含n个数，代表数组arr。

输出描述:

输出一个整数，代表出现次数大于一半的数，如果没有这样的数，请输出‘-1“。

示例1

输入

5
11 7 5 7 7

输出

示例2

输入

4
2 2 3 3

输出

-1

备注:

时间复杂度,额外空间复杂度。

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x;
    cin>>n;
    map<int, int> mp;
    for(int i=0;i<n;i++){
        cin>>x;
        mp[x]++;
    }
    for(auto &p: mp){
        if(p.second > n/2){
            cout<<p.first<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}

发表于 2020-05-13 07:30:47 回复(0)

Java

pein531

如果有这样的数存在，它一定是排完序后在中间的数，我们可以遍历一下数组再检查一下是不是出现次数大于数组长度的一半，以确保不输出-1。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] params = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(params[i]);
        Arrays.sort(arr);
        int target = arr[arr.length / 2], count = 0;
        for(int num: arr) if(num == target) count ++;
        System.out.println(count > arr.length / 2? target: -1);
    }
}

要想时间复杂度达到O(n)，可以用基于桶排序思想的排序方法。

发表于 2021-11-14 09:03:24 回复(0)

C/C++

奋斗之路不堵车

#include<iostream>
#include<map>
using namespace std;
int main()
{
int n,num;
while(cin>>n){
map<int,int> m;
bool flag=true;
for(int i=0;i<n;i++){
cin>>num;
m[num]++;
}
for(auto it:m){
if(it.second>n/2){
cout<<it.first<<endl;
flag=false;
}
}
if(flag) cout<<"-1"<<endl;
}
return 0;
}

发表于 2020-07-21 16:07:25 回复(0)

Python

郑骄阳

def max_count(arr):
	count = {}
	for i in set(arr):
		count[i] = arr.count(i)
	return count

num = input()
arr = input().split()
map = max_count(arr)
l = sorted(map.items(),key = lambda x:x[1])
if l[-1][-1] > len(arr)/2:
    print(l[-1][0])
else:
    print(-1)

case通过率为75.00%

有没有大神有完整的python解？

发表于 2020-05-18 21:07:10 回复(0)

牛客831188582号

有没有前端解法呢

发表于 2022-06-10 09:53:04 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
       
        int times = 0;
        int cand = 0;
        for(int i=0;i<n;i++){
            if(times==0){
                cand = arr[i];
                times++;
            }else if(arr[i] == cand){
                times++;
            }else{
                times--;
            }
        }
        times = 0;
         for(int i=0;i<n;i++){
            if(arr[i] == cand){
                times++;
            }
        }
        
        if(times > n/2){
            System.out.print(cand);
        }else{
            System.out.print("-1");
        }
        
		
	}
}

发表于 2019-10-24 11:10:39 回复(0)

blue_eyes

不知道算不算正解。反正AC了。用的哈希：

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n, x, t;
    vector<int> f(100005,0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        t = x*x % 100001;
        f[t]++;
        if (2 * f[t] > n) {
            cout << x;
            return 0;
        }
    }
     cout <<-1;
    return 0;
}

发表于 2019-09-30 11:24:43 回复(0)

这是您的offer请查收

#include<iostream>
#include<map>
using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        int temp=0;
        map<int, int>v;
        v.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            v[temp]++;
        }
        int k = n / 2;
        for(auto ptr=v.begin();ptr!=v.end();ptr++)
        {
            if(ptr->second>k)
            {
                cout<<ptr->first<<endl;
                return 0;
            }
        }
        cout<<"-1"<<endl;
    }
    return 0;
}

这个题用map做觉得很合适，正常读取数据放入map之中，同步更新key对应的value值，而后再进行一次遍历，通过value值找key，找到就是有，找不到就是没有，只需要遍历一次即可

发表于 2019-08-16 11:09:19 回复(0)

提交观点

问题信息

模拟查找

上传者：小小

难度：

8条回答 18收藏 4621浏览

通过挑战的用户

查看代码

牛客79923...

2023-03-04 16:46:32
DBCGary

2022-09-06 20:03:02
DDDVE

2022-08-26 08:15:14
szu_Edison

2022-08-18 12:25:28
Keen06

2022-08-13 13:36:45

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

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题