Guest User

Untitled

a guest
Mar 10th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.79 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.NavigableSet;
  5. import java.util.TreeSet;
  6.  
  7. import static java.lang.Integer.parseInt;
  8.  
  9. /**
  10.  * Created by bugkiller on 11/03/19.
  11.  */
  12. class KthLargestElementInStream {
  13.  
  14.     private static final int a[] = new int[1000000];
  15.  
  16.     public static void main(String[] args) throws IOException {
  17.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  18.         int t, n, k;
  19.         String s[];
  20.         t = parseInt(br.readLine());
  21.         while (t-- > 0) {
  22.             s = br.readLine().split("\\s");
  23.             k = parseInt(s[0]);
  24.             n = parseInt(s[1]);
  25.             s = br.readLine().split("\\s");
  26.             for (int i = 0; i < n; i++) {
  27.                 a[i] = parseInt(s[i]);
  28.             }
  29.             System.out.println(convertToString(kthLargest(a, n, k), n));
  30.         }
  31.     }
  32.  
  33.     static int[] kthLargest(int a[], int n, int k) {
  34.         NavigableSet<Integer> set = new TreeSet<>();
  35.         int result[] = new int[n];
  36.         for (int i = 0; i < n; i++) {
  37.             if (i < k) {
  38.                 set.add(a[i]);
  39.             } else {
  40.                 if (a[i] > set.first()) {
  41.                     set.pollFirst();
  42.                     set.add(a[i]);
  43.                 }
  44.             }
  45.             if (i < k - 1) {
  46.                 result[i] = -1;
  47.             } else {
  48.                 result[i] = set.first();
  49.             }
  50.         }
  51.         return result;
  52.     }
  53.  
  54.     private static String convertToString(int a[], int n) {
  55.         StringBuilder sbr = new StringBuilder();
  56.         for (int i = 0; i < n; i++) {
  57.             sbr.append(a[i]).append(" ");
  58.         }
  59.         sbr.deleteCharAt(sbr.length() - 1);
  60.         return sbr.toString();
  61.     }
  62. }
Add Comment
Please, Sign In to add comment