LC 1985 [M] Find the Kth Largest Integer in the Array - ALawliet/algorithms GitHub Wiki
# this question TLE if randomly choose pivot or array is all equal which leads to quadratic time complexity for quickselect
class Solution:
def kthLargestNumber(self, nums: List[str], k: int) -> str:
nums = [int(x) for x in nums] # convert str to nums so we can sort
shuffle(nums) # try to avoid worst case
n = len(nums)
T = n - k
l = 0
def partition(l, r): # hoare
i = l + 1
j = r - 1
while i <= j:
if nums[i] < nums[l]: # i l i
i += 1
elif nums[l] < nums[j]: # l j j
j -= 1
else:
nums[i], nums[j] = nums[j], nums[i] # i j ij
i += 1 ; j -= 1
nums[l], nums[j] = nums[j], nums[l] # l j
return j
r = n
while l < r:
p = partition(l, r)
if p == T:
return str(nums[p])
elif p < T:
l = p + 1
elif p > T:
r = p
# lomuto partition + equal normal binary search gives bad test case TLE if the array is all equal
# def partition(l, r):
# pivot = nums[r]
# i = l
# for j in range(l, r):
# if nums[j] <= pivot:
# nums[i], nums[j] = nums[j], nums[i]
# i += 1
# nums[i], nums[r] = nums[r], nums[i]
# return i
# r = n - 1
# while l <= r:
# p = partition(l, r)
# if p == T:
# return str(nums[p])
# elif p < T:
# l = p + 1
# elif p > T:
# r = p - 1