It's actually "linear time selection"(python)


  • 0
    class Solution(object):
        def select(self, nums, low, high):
            small_group_size = 5
            marks = range(low, high, small_group_size)[:-1]
            for mark in marks:
                nums[mark:mark+small_group_size] = sorted(nums[mark:mark+small_group_size])
            for i, mark in enumerate(marks):
                tmp = nums[mark + small_group_size // 2]
                nums[mark + small_group_size // 2] = nums[low + i]
                nums[low + i] = tmp
            nums[low:low + len(marks)] = sorted(nums[low:low + len(marks)])
            tmp = nums[low]
            nums[low] = nums[low + len(marks) // 2]
            nums[low + len(marks) // 2] = tmp
            return
    
        def partition(self, nums, low, high):
            i = low
            j = high
            pivot = nums[low]
            while i < j:
                while nums[j] > pivot and i < j:
                    j -= 1
                nums[i] = nums[j]
                while nums[i] <= pivot and i < j:
                    i += 1
                nums[j] = nums[i]
            nums[i] = pivot
            return i
    
        def r_k_max(self, nums, low, high, k):
            if high - low < k - 1:
                return None
            if high - low <= 5:
                return sorted(nums[low:high+1])[high - k + 1 - low]
            length = high - low
            self.select(nums, low, high)
            mid = self.partition(nums, low, high)
    
            if mid == high - k + 1:
                return nums[mid]
            if mid < high - k + 1:
                return self.r_k_max(nums, mid + 1, high, k)
            if mid > high - k + 1:
                return self.r_k_max(nums, low, mid - 1, mid - low - length + k - 1)
    
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            return self.r_k_max(nums, 0, len(nums) - 1, k)
    

Log in to reply
 

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