<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the</em> <code>k<sup>th</sup></code> <em>largest element in the array</em>.</p>

<p>Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></code> distinct element.</p>

<p>Can you solve it without sorting?</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,1,5,6,4], k = 2
<strong>Output:</strong> 5
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [3,2,3,1,2,4,5,5,6], k = 4
<strong>Output:</strong> 4
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums: List[int], k: int) -> int:
            pivot = random.choice(nums)
            left, mid, right = [], [], []
            for num in nums:
                if num > pivot:
                    left.append(num)
                elif num < pivot:
                    right.append(num)
                else:
                    mid.append(num)

            if len(left) >= k:
                return quick_select(left, k)
            if len(left) + len(mid) < k:
                return quick_select(right, k - len(left) - len(mid))
            return pivot
            
        return quick_select(nums, k)

    def findKthLargest6(self, nums: List[int], k: int) -> int:
        if not nums or k < 0: return 0
        from heapq import heappush, heappop
        q = []
        for num in nums:
            heappush(q, num)
            if len(q) > k:
                heappop(q)
        return q[0]

    def findKthLargest5(self, nums: List[int], k: int) -> int:
        if not nums: return 0
        import heapq
        # nums = nums * -1
        nums = [i * -1 for i in nums]
        # heapq.heapify(nums)
        # ans = 0
        # for i in range(k):
        #     ans = heapq.heappop(nums)
        # return -ans

    def findKthLargest4(self, nums: List[int], k: int) -> int:
        if not nums: return 0
        import heapq
        # nums = nums * -1
        nums = [i * -1 for i in nums]
        heapq.heapify(nums)
        ans = 0
        for i in range(k):
            ans = heapq.heappop(nums)
        return -ans

    def findKthLargest3(self, nums: List[int], k: int) -> int:
        if not nums or k < 0: return -1
        n = len(nums)
        if k > n: return -1
        import heapq
        q = []
        for num in nums:
            heapq.heappush(q, num)
            if len(q) > k:
                heapq.heappop(q)
        print(q)
        return q[0]

    def findKthLargest2(self, nums: List[int], k: int) -> int:    
        if not nums or k < 0: return -1
        n = len(nums)
        if k > n: return -1
        indexes = set()
        idx = -1
        max_num = -float("inf")
        for i in range(k):
            for j, num in enumerate(nums):
                if j in indexes: continue
                if num > max_num:
                    idx = j
                    max_num = num
            indexes.add(idx)
            if i < k - 1:
                max_num = -float("inf")
            # idx = -1
        return max_num

    def findKthLargest1(self, nums: List[int], k: int) -> int:
        if not nums or k < 0: return -1
        n = len(nums)
        if k > n: return -1
        nums.sort()
        return nums[n - k]
        

29937