QuickSelectでK番目までの値を求める。

以下の問題を解いた。

LeetCode - K Closest Points to Origin

ソートされてない配列からK番目までの値を求めろと言われると， とりあえずのPriorityQueueを使うことを考えた。 PriorityQueueつかうにしても以下の二通りが考えられるわけだが。

1. 全部突っ込んでk番目まで取り出す
2. k個以上になるときに，最も大きい値を削除する

あとは単純にソートしてもいいのかも。

まぁ，どちらでもPassはしたのだが解答をみると， でできるQuickSelectというアルゴリズムがあるらしい。 （が，この解答をそのままコピペしてもパスはしないという。。。）

QuickSelectは，ほとんどQuicksortで，必要ないところを枝刈りしている。 理想的な2分割できる状態を考えると，比較評価の回数はと分割するたびに比較評価の数が半分になり，これは極限をとると，つまりになる。ただ，最悪はとなって，かな。

class Solution {
    
    public int[][] kClosest(int[][] points, int k) {
        quickSelect(points, 0, points.length-1, k);
        return Arrays.copyOf(points, k);
    }

    private void quickSelect(int[][] p, int s, int e, int k){
        if (s >= e) return;

        int pivot = partition(p, s, e);
        if (pivot < k - 1) {
            quickSelect(p, pivot+1, e, k);
        } else if (pivot > k - 1) {
            quickSelect(p, s, pivot-1, k);
        }
    }

    private int partition(int[][] p, int s, int e) {
        int pivot = s + ThreadLocalRandom.current().nextInt(e - s + 1);
        swap(p, pivot, e);

        int threshold = dist(p[e]);
        int j = s;
        for (int i = s; i < e; ++i) {
            if (dist(p[i]) < threshold) {
                swap(p, i, j++);
            }
        }
        swap(p, j, e);
        return j;
    }

    private void swap(int[][] pts, int i, int j) {
        int[] tmp = pts[i];
        pts[i] = pts[j];
        pts[j] = tmp;
    }
    
    private int dist(int[] pt) {
        int x = pt[0];
        int y = pt[1];
        return x * x + y * y;
    }
}

同系統の問題。 Kth Largest Element in an Array