Topic describes

Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.

Example 1.

Input: [3,2,1,5,6,4] and k = 2 output: 5Copy the code

Example 2.

Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4Copy the code

Note: You can assume that k is always valid and that 1 ≤ k ≤ the length of the array.

Their thinking

The array they give us is unordered, so to get the KTH largest value in the array, we have to sort the array first, and then it’s easy to get the KTH largest value in the array.

Idea 1, array sort

[nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] [nums.length -k] In reverse order, the KTH largest element, nums[k-1], is the desired value.

Idea two, in situ fast row

Given a middle value, a left boundary left and a right boundary right, put everything less than the middle value to the left (or right) of the middle value, and everything greater than the middle value to the right (or left) of the middle value. Then it can be understood that there are now two regions, left and right. After that, the two regions can be recursed to realize the fast row in situ.

AC code

Solve an array sort

var findKthLargest = function (nums, k) {
    return nums.sort((a,b) => a-b)[nums.length - k]
}
Copy the code

Problem solving in place

/** * @param {number[]} nums * @param {number} k * @return {number} */ function partition(arr, left, Right) {if (left >= right) return Let private = arr[left] let I = left, J = right while (I < j) {while (arr[j] <= private && I < j) { While (arr[I] >= private &&i < j) {if (arr[I] = private &&i < j) {if (arr[I] = private &&i < j) {if (arr[I] = private &&i < j) {if (arr[I] = private &&i < j) {if (arr[I] = private &&i < j) {if (arr[I] = private &&i < j) { I ++} arr[j] = arr[I] private} arr[I] = private} arr[I] = private} arr[I] = private Partition (arr, I + 1, I + 1); partition(arr, I + 1); Function sort(arr) {partition(arr, 0); arr.length - 1) return arr } var findKthLargest = function (nums, k) { return sort(nums)[k-1] };Copy the code

conclusion

The related labels are heap and divide-and-conquer, but I only think of sorting, algorithm has a long way to go, tomorrow also want to refueling oh. If some friends think it is good, I hope you can click on it

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign