Find the K-th Largest

1. Problem Description

Given an integer array, use the idea of quicksort to find the K-th largest number in the array.

Given an integer array a, its size n, and K to find (K is between 1 and n), return the K-th largest number. The answer is guaranteed to exist.

2. Approach

1. Approach 1
   • Sort the array in order first, then take the n-k-th element after sorting
2. Approach 2
   • Modify partition based on quicksort
   • The principle is that a partition operation can always place one element in its final position, and can also tell where that element finally belongs

3. Implementation

3.1. Sorting

func findKthLargest(nums []int, k int) int {
    if len(nums) < k {
        return 0
    }
    sort.Slice(nums, func(i,j int) bool {
        return nums[i] > nums[j]
    })
    return nums[k-1]

}

3.2. Quicksort partition

func findKthLargest(nums []int, k int) int {
    return findKth(nums, 0, len(nums)-1, k)
}

func findKth(nums []int, left, right, k int) int {
    if left > right {
        return -1
    }

    p := partition(nums, left, right, k)
    if p == k-1{
        return nums[p]
    }else if p < k-1 {
        return findKth(nums, p+1, right, k)
    }else {
        return findKth(nums, left, p-1, k)
    }
}

func partition(nums []int, left, right, k int) int {
    pivot := nums[left]
    for left < right {
        for left < right && nums[right] <= pivot {
            right--
        }
        nums[left], nums[right] = nums[right],nums[left]
        for left < right && nums[left] >= pivot {
            left++
        }
        nums[left], nums[right] = nums[right],nums[left]
    }
    nums[left] = pivot
    return left
}

4. References

• Find the Kth Largest - NowCoder
• Partition-Based Decrease-and-Conquer + Priority Queue (Java, C++, Python) - Kth Largest Element in an Array - LeetCode