# 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（两者等价）
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2025/215.-kth-largest-element-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.