fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. /* Name of the class has to be "Main" only if the class is public. */
  7. class Ideone
  8. {
  9. 	public static void main (String[] args) throws java.lang.Exception
  10. 	{
  11. 		int[][] input = new int[][] {
  12.                 {1,   2,   3,    4},
  13.                 {8,   9,   10,  11},
  14.                 {33, 44,   55,  66},
  15.                 {99, 150, 170, 200}
  16.         };
  17.         for (int i = 1; i <= 16; i ++) {
  18.         	System.out.println(findkthLargestElement(input, i, 4, 4));	
  19.         }
  20.  
  21. 	}
  22.  
  23. 	public static int findkthLargestElement(int[][] input, int k, int m, int n) {
  24.         if (m <=1 || n <= 1 || k > m * n ) {
  25.             return Integer.MIN_VALUE;
  26.         }
  27.         int i = 0;
  28.         int j = 0;
  29.         if (k < m && k < n) {
  30.             i = m - k;
  31.             j = n - k;
  32.         }
  33.         PriorityQueue<Element> maxQueue = new PriorityQueue(m, new Comparator<Element>() {
  34.             @Override
  35.             public int compare(Element a, Element b) {
  36.                 return b.value - a.value;
  37.             }
  38.         });
  39.  
  40. 		Map<Integer, Integer> colMap = new HashMap<Integer, Integer>();
  41.         for (int row = i; row < m; row++) {
  42.             Element e = new Element(input[row][n - 1], row, n - 1);
  43.             colMap.put(row, n - 1);
  44.             maxQueue.add(e);
  45.         }
  46.         Element largest = new Element(0, 0, 0);
  47.         for (int l = 0; l < k; l++) {
  48.             largest = maxQueue.poll();
  49.             int row = largest.row;
  50.             colMap.put(row, colMap.get(row) - 1);
  51.             int col = colMap.get(row);
  52.             while (col < j && row > i) {
  53.                 row = row - 1;
  54.                 colMap.put(row, colMap.get(row) - 1);
  55.                 col = Math.max(0, colMap.get(row));
  56.             }
  57.  
  58.             Element nextLargest = new Element(input[row][Math.max(0, col)], row, Math.max(0, col));
  59.             maxQueue.add(nextLargest);
  60.         }
  61.         return largest.value;
  62.     }
  63.  
  64.     private static class Element {
  65.         int value;
  66.         int row;
  67.         int col;
  68.  
  69.         public Element(int value, int row, int col) {
  70.             this.value = value;
  71.             this.row = row;
  72.             this.col = col;
  73.         }
  74.     }
  75. }
  76.  
  77.  
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
1
stdout
copy 
200
170
150
99
66
55
44
33
11
10
9
8
4
3
2
1
https://ideone.com/wIeZSo
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!