Problem

Find K-th largest element in N arrays.

Notice

You can swap elements in the array

Example

In n=2 arrays [[9,3,2,4,7],[1,2,3,4,8]], the 3rd largest element is 7.

In n=2 arrays [[9,3,2,4,8],[1,2,3,4,2]], the 1st largest element is 9, 2nd largest element is 8, 3rd largest element is 7 and etc.

思路

• 多个数组中要求出第k个最大, 那么需要先把数组都排好序才能开始比较
• 然后用maxheap.
• 为什么不用minheap? 因为, 使用minheap是在单个数组无序的情况下使用

    class Element {
        int r;
        int c;
        int val;
        public Element (int r, int c, int val) {
            this.r = r;
            this.c = c;
            this.val = val;
        }
    }
    public int KthInArrays(int[][] arrays, int k) {
        if (arrays == null || arrays.length == 0) {
            return -1;
        }
        int r = arrays.length;
        PriorityQueue<Element> heap = new PriorityQueue<>(k, new Comparator<Element>() {
            public int compare (Element e1, Element e2) {
                return e2.val - e1.val;
            }
        });
        for (int i = 0; i < r; i++) {
            Arrays.sort(arrays[i]);
            int len = arrays[i].length;
            if (len > 0)
                heap.offer(new Element(i, len - 1, arrays[i][len - 1]));
        }

        while (!heap.isEmpty()) {
            Element curt = heap.poll();
            k--;
            if (k == 0) return curt.val;
            if (curt.c > 0) {
                heap.offer(new Element(curt.r, curt.c - 1, arrays[curt.r][curt.c - 1]));
            }
        }
        return -1;
    }