K - Largest Element of Array

Asagidaki soruda yapmamiz istenen verilen arraydaki k largest elementi bulmak.

Ornegin

arr[] = [3, 2, 1, 5, 6, 4], ve k =2 icin once siralayalim

1 2 3 4 5 6. burdaki en buyuk 2. eleman 5 oldugu icin output 5 olmalidir.

Cozume gecelim.

Nasil cozeriz :
 Once siralariz. Sonra da sondan k. elemani buluruz.

import java.util.Arrays;
import java.util.PriorityQueue;
public class KLargestElement {
 public static int kLargest(int[] arr, int k) {
  Arrays.sort(arr);
  return arr[arr.length - k];  
 } 
 public static void main(String[] args) {
  int arr[] = new int[] {3, 2, 1, 5, 6, 4};
  System.out.println(kLargest(arr, 2));
  
  int arr2[] = new int[] {3, 2, 3, 1, 2, 4, 5, 5, 6};
  System.out.println(kLargest(arr2, 4));
 }
}

Burda once siraladik sonra da sondan k. elemani bulduk. Islemin time completixy si O(nlogn) dir. Cunku siralama yaptigimiz icin .

Daha effektif yapmaya calisalim. Bunun icin heap kullanalim.

Elemanlari tek tek heap e eklerken, eger heap in size i k den buyukse ilk elemani cikaralim. Bu sekilde yaptigimizda elimizde en son k eleman kalmis olur. Bizde ilk elemani dondurursek o eleman k largest elemanimiz olur.

import java.util.Arrays;
import java.util.PriorityQueue;
public class KLargestElement {
 public static int kLargest(int[] arr, int k) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
  for(int num : arr) {
    minHeap.add(num);
    if(minHeap.size() > k) {
     minHeap.remove();
    }
  }
  return minHeap.remove();
 } 
 public static void main(String[] args) {
  int arr[] = new int[] {3, 2, 1, 5, 6, 4};
  System.out.println(kLargest(arr, 2));
         int arr2[] = new int[] {3, 2, 3, 1, 2, 4, 5, 5, 6};
  System.out.println(kLargest(arr2, 4));
 }
}

Burada array i sort etmiyoruz. Heap kullaniyoruz. Burda ise time O(n) dir.