ペアの個数を求める方法

ペアの個数

小ネタです。intの整数値 x, y の座標 (x, y)n 個与えられたときに、x_i = x_k, y_i = y_k となる座標の組み合わせが何個あるかを数える方法。
例えば、(1, 1),(2, 2),(2, 3),(2, 2),(1, 1) という座標が与えられたときは、
(1, 1)2
(2, 2)2
(2, 3)1
ということになります。標準出力する際にデコードしているので若干煩雑になっています。

これは、intが32bitであることを利用して、ハッシュ値code = (long)x << 32 | yとすれば良いです。あとはMap等を使用して要素の個数を集計すれば良いです。

実装例

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class Sample {

    public static void main(String[] args) throws IOException {

        int n = 5;
        Point[] ps = new Point[n];
        ps[0] = new Point(1, 1);
        ps[1] = new Point(2, 2);
        ps[2] = new Point(2, 3);
        ps[3] = new Point(2, 2);
        ps[4] = new Point(1, 1);

        Map<Long, Integer> map = new HashMap<Long, Integer>();
        for (int i = 0; i < n; i++) {
            long code = (long)ps[i].x<< 32 | ps[i].y;
            map.merge(code, 1, Integer::sum);
        }

        for (Long entry : map.keySet()) {
            System.out.println("("+(entry >> 32)+","+ (entry & ((long)1<<32)-1)+") -> "+map.get(entry));
        }
    }

    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

出力結果

(2,2) -> 2
(1,1) -> 2
(2,3) -> 1