Record 1 algorithm problem
The KTH large element in the array
Leetcode-cn.com/problems/kt…
Ps: Pile on another oneThe articleDetailed introduction. I don’t want to repeat it so you can skip over it. The heap code for this problem is going to be written right at the end.
The easiest way to do this is to sort and return the element with index k minus 1.
function findKthLargest(nums, k) {
nums.sort((a, b) = > b - a)
return nums[k - 1]}Copy the codeThis seems too simple, we can do something by hand, for example, through the quick list, or pile to answer the questions.
1. The fast row
Quicksort is basically taking a reference point, and putting the number greater than it to the left and the number less than it to the right. Left or right depends on whether you want to go up or down.
This recursive method of cutting a big problem into smaller problems is called divide-and-conquer. The termination condition of recursion is that there is only one element in the interval, so it just returns.
But what we’re going to find is that as long as the first k is in descending order or ascending order, we know what the KTH largest element or the KTH smallest element is. So when the KTH number we want is to the left of the reference point, we recurse to the left of the array, and vice versa, and we cut the work in half. If the KTH happens to be the reference point, it just returns without doing any recursion.
[3, 2, 5, 6, 7] let's say our base point is 5, and then for the second largest element we just recurse 3, 2Copy the codeThe intuitive way to write quicksort is to recursively generate two arrays at a time and concatenate them on return. Such as:
/ / pseudo code
const left = []
const right = []
if (arr[i] > 基准点) {
right.push(arr[i])
} else {
left.push(arr[i])
}
returnRecursion (left), reference point, recursion (right)Copy the codeAnother space-complexity operation is to sort directly on the original array, but how to swap nodes is a critical and difficult problem. Is one of the main points of this article.
This is where Pointers come in, and to facilitate swapping, we need to set the reference point to the beginning of the array, arr[0].
Let’s say we have a swap function, swap, that passes in arrays and subscripts and swaps automatically.
You can always fix the first one in that array as your reference point, or you can pick a random number as your reference point, and you can use the random number as your reference point.
First, since we are operating on the original array, we only have the starting and ending indices of the interval, not necessarily 0 and arr.length-1.
// Take the random subscript of this interval
let pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left
const pivot = arr[pivotIdx]
swap(arr, left, pivotIdx)
pivotIdx = left
left += 1
/* * select * from 'a' where 'left' and 'right' are sorted. * [a, b, c, d, e, f] * left right */
Copy the codeThen, we use the for loop to iterate over the nodes in the interval, swapping when they are larger than A, and we need a new pointer that points to the boundary that can be swapped. We can use left here, because it doesn’t do anything else.
When we judge that it is larger than the reference point, we swap the I node of the current for loop with the left. After swapping left++, the value before left is larger than the reference point by slowly zooming out. Partitions occur because they are swapped as soon as they are found to be larger than the reference point.
Also, the conditions that determine ascending or descending order are extracted, as is the rule of sort. Compare = (a, b) => b – a.
for(let i = left; i <= right; i++) {
if (compare(arr[i], pivot) < 0) {
swap(arr, i, left)
left++
}
}
// After the split, we know that the last left was incremented by 1 after the last swap.
// Left-1 is the first element to the left of the datum. Let's say [4, 5, 6, 3, 2] 6 is the last swap.
// He swaps with the reference point and puts the reference point in the right place. [6, 5, 4, 3, 2]
swap(arr, pivotIdx, left - 1)
// Then return the subscript of the reference point
return left - 1
// The following examples are in ascending order, when exchanged in hours over datum
// [3, 4, 6, 2, 1]
/* 3 i 1 index 1 -- 4 < 3 4 i 2 index 1 -- 6 < 3 6 i 3 index 1 -- 2 < 3 --> index 2 [3, 2 , 6, 4, 1 I 4 index 2 -- 1 < 3 --> index 3 [3, 2, 1, 4, 6] 1 I 5 break 2 */
// [3,2,1,5,6,4] 2
/* 3 i index 1 2 i 1 index 1 2 < 3 --> index--2 [3, 2, 1, 5, 6, 4] 1 i 2 index 2 1 < 3 --> index--3 [3, 2, 1, 5, 6, 4] 5 I 3 index 3 5 < 3 6 I 4 index 3 6 < 3 4 I 5 index 3 4 < 3
Copy the codeWe’re going to do the recursion. So what recursion does is it’s very simple, it splits the array over and over again. In order to do subtraction in this step, first we need to know the index of the KTH element, so we pass it in as an argument to the function. It then performs a binary recursive operation depending on whether the index of the KTH element is to the left or right of the reference point.
function quickSort(arr, k, left = 0, right = arr.length) {
constDatum subscript = segmentation (ARR, left, right)// Select the interval to the left of the reference point or the interval to the right of the reference point
if(base subscript < k) {quickSort(arr, k, left, base subscript -1)}else if(base subscript > k) {quickSort(arr, k, base subscript +1, right)
}
}
Copy the codeAnd in order to deal with the recursive termination condition, we need left < right, they can’t be equal, at least two elements in the interval.
Above is the quick sorting of the analysis, the complete code is as follows.
function findKthLargest(nums, k) {
quickSort(nums, k - 1)
return nums[k - 1]}function quickSort(arr, k, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIdx = partition(arr, left, right)
if (pivotIdx > k) {
quickSort(arr, k, left, pivotIdx - 1)}else if (pivotIdx < k) {
quickSort(arr, k, pivotIdx + 1, right)
}
}
return arr
}
// Ascending descending judgment
const compare = (a, b) = > b - a
function partition(arr, left, right) {
let pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left
const pivot = arr[pivotIdx]
swap(arr, pivotIdx, left)
pivotIdx = left
left = left + 1
for (let i = left; i <= right; i++) {
if (compare(arr[i], pivot) < 0) {
swap(arr, i, left)
left++
}
}
swap(arr, pivotIdx, left - 1)
return left - 1
}
function swap(arr, n1, n2) {
;[arr[n1], arr[n2]] = [arr[n2], arr[n1]]
}
Copy the codeThe heap
Ps again: heap in anotherThe articleDetailed introduction. I don’t want to repeat it so you can skip over it.
The complete code for this question is as follows:
function findKthLargest(nums, k) {
const heap = new Heap()
for(let i = 0; i < nums.length; i++) {
// The top of the heap is the smallest element in the largest heap
// The smallest heap is the opposite
if(heap.size() === k && heap.data[0] > val ) {
continue
}
heap.push(nums[i])
if (heap.size() > k) {
heap.pop()
}
}
return heap.data[0]}class Heap {
constructor() {
this.data = []
this.compare = (a, b) = > a - b
}
size() {
return this.data.length
}
swap(n1, n2) {
const { data } = this
const temp = data[n1]
data[n1] = data[n2]
data[n2] = temp
}
push(val) {
this.data.push(val)
this.bubblingUp(this.size() - 1)}pop() {
if (this.size() === 0) return null
const { data } = this
const discard = data[0]
const newMember = data.pop()
if (this.size() > 0) {
data[0] = newMember
this.bubblingDown(0)}return discard
}
bubblingUp(index) {
while (index > 0) {
const parent = (index - 1) > >1
const { data } = this
if (this.compare(data[index], data[parent]) < 0) {
this.swap(parent, index)
index = parent
} else {
break}}}bubblingDown(index) {
const { data } = this
const last = this.size() - 1
while (true) {
const left = index * 2 + 1
const right = index * 2 + 2
let parent = index
if (left <= last && this.compare(data[left], data[parent]) < 0) {
parent = left
}
if (right <= last && this.compare(data[right], data[parent]) < 0) {
parent = right
}
if(index ! == parent) {this.swap(index, parent)
index = parent
} else {
break}}}}Copy the code