Search

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.




Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.


Solution:


1. Sorting:

class Solution {public int findKthLargest(int[] nums, int k) 
  {       
        Arrays.sort(nums);
        return nums[nums.length -k];
    }


2. Heap:


 public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for(int i: nums){
            queue.offer(i);
            if(queue.size()>k){
                queue.poll();
            }
        }
        return queue.peek();
    }


3. Partitioning:

class Solution {
    public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    int left = 0;
    int right = n - 1;

    Random rand = new Random(0);

    while (left <= right) {
      int choosenIndex = rand.nextInt(right - left + 1) + left;

      int finalIndex = partition(nums, left, right, choosenIndex);
      if (finalIndex == n - k) {
        return nums[finalIndex];
      } else if (finalIndex > n - k) {
        right = finalIndex - 1;
      } else {
        left = finalIndex + 1;
      }
    }

    return -1;
  }

  private int partition(int[] arr, int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    int lesserIndex = left;
    swap(arr, pivotIndex, right);

    for (int i = left; i < right; i++) {
      if (arr[i] < pivotValue) {
        swap(arr, i, lesserIndex);
        lesserIndex++;
      }
    }

    swap(arr, right, lesserIndex);

    return lesserIndex;
  }

  private void swap(int[] arr, int first, int second) {
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
  }
}


13 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.