Swift solution - Divide and Conquer


  • 0
    class Solution {
        func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
            if nums.count == 0 {
                return 0
            }
            
            return helper(nums, 0, nums.count - 1, nums.count - k)
        }
        
        private func helper(_ nums: [Int], _ start: Int, _ end: Int, _ k: Int) -> Int {
            if start > end {
                return 0
            }
            
            let pivot = nums[end]
            var nums = nums
            var left = start
            
            for i in start..<end {
                if nums[i] <= pivot {
                    if left != i {
                        swap(&nums[left], &nums[i])
                    }
                    left += 1
                }
            }
            if left != end {
                swap(&nums[left], &nums[end])
            }
            
            if left == k {
                return nums[left]
            } else if left < k {
                return helper(nums, left + 1, end, k)
            } else {
                return helper(nums, start, left - 1, k)
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.