ac

给定一个整型数组arr，再给定一个整数k，打印所有出现次数大于n/k的数，如果没有这样的数,请打印”-1“

时间复杂度O(n * k),额外空间复杂度O(k)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            arr[i] = val;
        }
        // 获取可能的候选项
        Map<Integer, Integer> cands = new HashMap<>();
        for(int i=0;i<n;i++){
            if(cands.containsKey(arr[i])){
                cands.put(arr[i], cands.get(arr[i]) + 1);
            }else {
                if(cands.size() == k-1){
                    allCandsMinusOne(cands);
                }else {
                    cands.put(arr[i], 1);
                }
            }
        }
        //  确认候选项
        Map<Integer, Integer> candsReal = new HashMap<>();
        for(int i=0;i<n;i++){
            if(cands.containsKey(arr[i])){
                candsReal.put(arr[i], candsReal.getOrDefault(arr[i], 0) + 1);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for(Integer cand: candsReal.keySet()) {
            if (candsReal.get(cand) > (n / k)){
                ans.add(cand);
            }
        }
        if(ans.isEmpty()){
            System.out.println(-1);
            return;
        }
        // print 结果
        System.out.print(ans.get(0));
        for(int i=1;i<ans.size();i++){
            System.out.print(" " + ans.get(i));
        }
        System.out.println();
    }

    static void allCandsMinusOne(Map<Integer, Integer> cands){
        List<Integer> rmKeyList = new ArrayList<>();
        for(Integer cand: cands.keySet()){
            int val = cands.get(cand);
            if(val == 1){
                rmKeyList.add(cand);
            }else {
                cands.put(cand, val - 1);
            }
        }
        for(Integer rmCand: rmKeyList){
            cands.remove(rmCand);
        }
    }

}
/*
7 7
1 2 3 1 2 3 4

1 2 3

4 1
1 1 2 3

-1
*/