This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

1. Sort

So the first thing we want to do is sort the array, let’s say it’s in ascending order K and the big element is the index K minus 1. The:

  • The complexity of the algorithm = the complexity of the sorting algorithm.

The alternative sorting algorithms are quicksort, heap sort, and so on.

Time complexity analysis

  • Quick sort: O(nlogn)
  • Heap sort: O(nlogn)

Spatial complexity analysis

  • Quick sort: O(1)
  • Heap sort (operating on an array) : O(1)

2. Quicksort optimization

Our goal is to find the KTH element in the array, and we don’t really care if the elements are ordered. So sorting the array actually a lot of the comparisons are not what we expect. So how do you optimize? Just to review quicksort, this is a typical divide-and-conquer algorithm. Our quicksort of array a[l… r] is as follows (see Introduction to Algorithms) :

  • Decomposition: “divide” the array A [L… r] into two subarrays A [L… q−1] and A [q+1… r], such that each element of a[L… q−1] is less than or equal to a[q]a[q], and a[q] A [q]a[q] is less than or equal to each element of a[q+1… r]. The calculation of subscript QQ is also part of the “partition” process.
  • Solve: Sort the subarrays A [L… q−1] and a[q+1… r] by recursively calling quicksort.
  • Merge: Because subarrays are addressable, there is no need to merge. A [l… r] is already sorted.
  • The partitioning process mentioned above is to select any element x from the subarray A [L… r] as the primary element, adjust the elements of the subarray so that all the elements on the left are less than or equal to it, and all the elements on the right are greater than or equal to it, and the final position of x is Q.

Did you see anything? Divide-and-conquer means we don’t have to deal with the part that doesn’t contain the answer.



So whenever q is the KTH index to the last, we’ve got the answer.

Time complexity analysis

  • O(n)

The proof process can be referred to “Introduction to Algorithms” 9.2: Selection Algorithms with linear expectation “.

Spatial complexity analysis

  • O(1)

Three, code implementation

class Solution { Random random = new Random(); public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k); } public int quickSelect(int[] a, int l, int r, int index) { int q = randomPartition(a, l, r); if (q == index) { return a[q]; } else { return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index); }} public int int (int[] a, int l, int r) {int I = random.nextint (r-l + 1) + l; swap(a, i, r); return partition(a, l, r); } public int partition(int[] a, int l, int r) { int x = a[r], i = l - 1; for (int j = l; j < r; ++j) { if (a[j] <= x) { swap(a, ++i, j); } } swap(a, i + 1, r); return i + 1; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }}Copy the code