leetcode: 215. Kth Largest Element in an Array

problem

• https://leetcode.com/problems/kth-largest-element-in-an-array/

sort

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        nums.sort()
        return nums[nums.size - k]
    }
}

heap

class Solution {
    
    fun findKthLargest(nums: IntArray, k: Int): Int {
        // max heap
        val queue = PriorityQueue<Int>(compareBy { -it })
        nums.forEach { num ->
            queue.add(num)
        }
        repeat(k - 1) {
            queue.poll()
        }
        return queue.poll()
    }
}

quick select

class Solution {
    
    fun findKthLargest(nums: IntArray, k: Int): Int {
        val size = nums.size
        // largest k is equal to smallest (size - k)
        val index = size - k
        var start = 0
        var end = size - 1
        while (start < end) {
            val pivot = partition(nums, start, end)
            // does not need to consider left side
            if (pivot < index) start = pivot + 1
            // does not need to consider right side
            else if (pivot > index) end = pivot - 1
            else return nums[pivot]
        }
        // whether nums[start], nums[end] is OK.
        // because while condition is false when start == end
        return nums[start]    
    }
    
    fun partition(nums: IntArray, start: Int, end: Int): Int {
        val pivot = start
        var _s = start
        var _e = end
        while (_s <= _e) {
            while (_s <= _e && nums[_s] <= nums[pivot]) _s++
            while (_s <= _e && nums[_e] >= nums[pivot]) _e--
            if (_s > _e) break
            
            val temp = nums[_s]
            nums[_s] = nums[_e]
            nums[_e] = temp
        }
        val temp = nums[pivot]
        nums[pivot] = nums[_e]
        nums[_e] = temp
        return _e
    }
}