<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>

/*
 * @lc app=leetcode id=215 lang=cpp
 *
 * [215] Kth Largest Element in an Array
 */

// @lc code=start
class Solution {
 public:
  int findKthLargest(vector<int>& A, int k) {
    int n = A.size();
    k = n - k;
    return quick_select(A, 0, n - 1, k);
  }

  int quick_select(vector<int>& A, int l, int r, int k) {
    while (l < r) {
      int i = l, j = r, piv = A[l + (r - l >> 1)];
      while (i <= j) {
        while (A[i] < piv) i++;
        while (A[j] > piv) j--;
        if (i <= j) swap(A[i++], A[j--]);
      }

      if (k <= j) r = j;
      else if (k >= i) l = i;
      else break;
    }
    return A[k];
  }
};
// @lc code=end

57900