Idea: Quicks sort is considered here for its time complexity is only O(nlogn)
While it is unnecessary to reorder other side(aimed value unattended) of array, so the time complexity reduced to O(n)
class Solution:
# @param k & A a integer and an array
# @return ans a integer
def kthLargestElement(self, k, A):
position = len(A)-1 - self.quicksort(A, 0, len(A)-1, k-1)
return A[position]
def quicksort(self, A, low, high, k):
pivot = self.find_pivot(A,low, high)
if pivot > k:
position = self.quicksort(A, low, pivot-1, k)
return position
else:
if pivot < k:
position = self.quicksort(A, pivot+1, high, k)
return position
else:
return pivot
def find_pivot(self, A, low, high):
pivot = high
leftwall = low
for i in range(low, high):
if A[i] < A[pivot]:
A[leftwall], A[i] = A[i], A[leftwall]
leftwall +=1
A[high], A[leftwall] = A[leftwall], A[high]
return leftwall
网友评论