# 215. Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return *the* `k`<sup>`th`</sup> *largest element in the array*.

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

Can you solve it without sorting?

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,2,1,5,6,4], k = 2
</strong><strong>Output: 5
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
</strong><strong>Output: 4
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= k <= nums.length <= 10`<sup>`5`</sup>
* `-10`<sup>`4`</sup>` ``<= nums[i] <= 10`<sup>`4`</sup>

分析

注意第k大就是N-K+1小，N-K就是索引。所以后面直接返回nums\[k]

partition函数每次返回左范围右边界。

注意判断条件是l<=r，对比二分l+1\<r

```
def findKthLargest(nums, k):
    n = len(nums)
    k = n - k  # 转换为第k小的索引
    low, high = 0, n - 1
    
    while low <= high:
        pivot_pos = partition(low, high)
        
        if pivot_pos < k:
            low = pivot_pos + 1
        elif pivot_pos > k:
            high = pivot_pos - 1
        else:
            return nums[k]
    return nums[k]

def partition(low, high):
    pivot = nums[(low + high) // 2]
    l, r = low, high
    while l <= r:
        while l <= r and nums[l] < pivot: l += 1
        while l <= r and nums[r] > pivot: r -= 1
        if l <= r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
    return r  # 或者 return l-1（两者等价）
```