Mapで集計してからソートする系問題（AtCoder)

けっこうよく見るタイプなので、メモとして色々な解き方を書いておく。

・問題文

1~Nまでの数字が３回出現する。
２回目に出現するのが早い順に出力する問題。
例：1 3 3 3 2 2 1 1 2 　←１～３までの数字が３回ずつ出現。

atcoder.jp

解き方１：答えがわかった時点で出力

出現回数系はこういう解き方ができる。ソートしない。

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n * 3];

        // 2回目出現時点で答えを出力。ソートしない。一番シンプル。AC
        Map<Integer, Integer> map = new HashMap<>(); // 出現数字、出現回数

        for (int i = 0; i < 3 * n; i++) {
            a[i] = sc.nextInt() - 1;

            if (map.containsKey(a[i])) {

                if (map.get(a[i]) == 1) {
                    map.put(a[i], map.get(a[i]) + 1);
                    System.out.print(a[i] + 1 + " "); // 答え出力
                }

            } else {
                map.put(a[i], 1);
            }
        }

解き方２：Listに追加

答えとして出力したい順にListに追加。ソートしない。

上とやってることは同じ。

//         Listに追加バージョン。やってることは上と同じ。AC。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n * 3];

                Map<Integer, Integer> map = new HashMap<>(); // 出現数字、出現回数
                List<Integer> list = new ArrayList<>(n);
        
                for (int i = 0; i < 3 * n; i++) {
                    a[i] = sc.nextInt() - 1;
        
                    if (map.containsKey(a[i])) {
        
                        if (map.get(a[i]) == 1) {
                            map.put(a[i], map.get(a[i]) + 1);
                            list.add(a[i]); //Listに追加
                        }
        
                    } else {
                        map.put(a[i], 1);
                    }
                }
        
                for (int ans : list) {
                    System.out.print(ans + 1 + " ");
                }

解き方３：HashMap→２次元配列に移し替え→２次元配列をソート

集計はMapでして、２次元配列に移し替えてからソート。

問題変わっても色々使えそう。

       //　Map→２次元配列→２次元配列をソート。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n * 3];

                Map<Integer, Integer> map = new HashMap<>(); // 出現数字、出現回数
                int[][] soeji = new int[n][2];// [n]{出現数字, 出現箇所}
         
                for (int i = 0; i < 3 * n; i++) {
                    a[i] = sc.nextInt() - 1;
         
                    if (map.containsKey(a[i])) {
         
                        if (map.get(a[i]) == 1) {
                            map.put(a[i], map.get(a[i])+1);
                            soeji[a[i]][0] = a[i];// ２次元配列に格納
                            soeji[a[i]][1] = i;
                        }
         
                    } else {
                        map.put(a[i], 1);
                    }
                }
                // ２個めの要素（出現箇所）でソート 
                Arrays.sort(soeji, (aa, bb) -> aa[1] - bb[1]);
         
                for (int i = 0; i < soeji.length; i++) {
                    System.out.print(soeji[i][0] + 1 + " ");
                }

解き方４：HashMap→TreeMapでソート

HashMapで集計→TreeMapに移し替えてソート。

ちょっと変な書き方。あんまり使わないかな。

       // HashMap→TreeMapでソートする。ACだがごちゃごちゃ。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n * 3];

                Map<Integer, int[]> map = new HashMap<>();// key:出現数字、value:出現回数、出現箇所
                Map<Integer, Integer> tree = new TreeMap<>();//出現箇所、出現数字
                for (int i = 0; i < 3 * n; i++) {
                    a[i] = sc.nextInt() - 1;
        
                    if (map.containsKey(a[i])) {
        
                        if (map.get(a[i])[0] == 1) {
                            int[] b = new int[2];//出現回数、出現箇所
                            b[0] = 2;
                            b[1] = i;
                            map.put(a[i], b);
                        }
        
                    } else {
                        int[] b = new int[2];//出現回数、出現箇所
                        b[0] = 1;
                        b[1] = i;
        
                        map.put(a[i], b);
                    }
                }
        
                // TreeMapでソートする
                for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                    int key = entry.getKey() + 1;//出現数字
                    int val = entry.getValue()[1];//出現箇所
        
                    tree.put(val, key);
                }
        
                for (Map.Entry<Integer, Integer> entry : tree.entrySet()) {
        
                    System.out.print(entry.getValue() + " ");
                }