# Question

Formatted question description: https://leetcode.ca/all/215.html

# 215. Kth Largest Element in an Array

Medium

## Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2

Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4

Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

# Algorithm

Heap or directly sorting can solve it, but kind of cheating.

The idea of Quick Sort, where the sorting direction is from big to small.

The core idea is to find a pivot point Pivot every time, and then traverse all other numbers, like this question from big to small, put the numbers greater than the pivot point to the left half, and put the numbers less than the pivot point to the right half. In the right half, the pivot point is the largest number in the entire array.

Although the left and right parts are not necessarily completely ordered, it does not affect the result of this question. Because all the values in the left half are greater than any value in the right half, we check the position of the pivot point:

• If it happens to be k-1, then directly return the number at that position;
• If it is greater than k-1, it means that the required number is in the left half, update the right boundary, and then find the new pivot point
• otherwise, update the right half and find the position of the pivot

Java