215.md

Kth Largest Element in an Array

Description

link

---

Solution

• See Code

---

Code

O(nlogn)

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        s, e = 0, len(nums)-1
        while s <= e:
            rand = random.randint(s, e)
            nums[rand], nums[e] = nums[e], nums[rand]
            i = s
            for j in range(s, e):
                if nums[j] > nums[e]:
                    nums[i], nums[j] = nums[j], nums[i]
                    i+=1
            nums[i], nums[e] = nums[e], nums[i]
            if i == k-1:
                return nums[i]
            elif i < k-1:
                s = i+1
                k-=(i-s+1)
            else: 
                e = i-1
        return -1