首页 > 试题广场 >

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

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

输入描述:
输入包含两行，第一行输入包含两个整数n和k,第二行包含n个整数，代表数组arr。


输出描述:
输出所有出现次数大于n/k的数，如果没有这样的数,请输出”-1“。
示例1

输入

7 7
1 2 3 1 2 3 4

输出

1 2 3
示例2

输入

4 1
1 1 2 3

输出

-1

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
Java
阿基米德__头像 阿基米德__
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);
        int a = n / k;
        String[] s2 = in.nextLine().split(" ");
        int[] array = new int[s2.length] ;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < s2.length; j++) {
            array[j] = Integer.parseInt(s2[j]);
            map.put(array[j], map.getOrDefault(array[j], 0) + 1);
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > a) {
                System.out.print(entry.getKey()+" ");
                count++;
            }
        }
        if(count==0){
            System.out.print("-1");
        }
       
    }
}
发表于 2023-09-14 18:02:27 回复(0)
Java
pein531头像 pein531
还是不整花里胡哨的快啊 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] strArr = br.readLine().split(" ");
        long[] arr = new long[n];
        HashMap<Long, Integer> counter = new HashMap<>();
        for(int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(strArr[i]);
            counter.put(arr[i], counter.getOrDefault(arr[i], 0) + 1);
        }
        boolean flag = false;
        for(long key: counter.keySet()){
            if(counter.get(key) > n / k) {
                flag = true;
                System.out.print(key + " ");
            }
        }
        if(!flag) System.out.println(-1);
    }
}

发表于 2021-11-14 17:14:46 回复(0)
Java
牛客617355593号头像 牛客617355593号
import java.util.*;

public class Main{
    
    public static void main (String [] args){
        
        Scanner s = new Scanner (System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        
        int [] num = new int[n];
        Map<Integer,Integer> map = new HashMap<Integer,Integer>(); 
        for(int i=0;i<n;i++){
            num[i] = s.nextInt();
            if(map.containsKey(num[i])){
                map.put(num[i],(map.get(num[i])+1));
            }else{
               map.put(num[i],1); 
            }
        }
        boolean flag = true;
        for(Map.Entry<Integer,Integer> en: map.entrySet()){
            if(en.getValue() >(n/k)){
                System.out.print(en.getKey()+" ");
                flag = false;
            }
        }
        if(flag){
            System.out.print(-1);
        }
    }
}
发表于 2021-11-08 11:34:24 回复(0)
提交观点

问题信息

模拟 哈希
上传者：小小
难度：
4条回答 4877浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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