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

• ``````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)
``````

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