top of page
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;
  }
}


16 views0 comments

Recent Posts

See All

Minimum Deletions to Make Character Frequencies Unique

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

Smallest String With A Given Numeric Value

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.

Comments


bottom of page