Topic link

Standing on the shoulders of giants

Train of thought

Direct use of the original method of sorting backwards after the value, trick way, ha ha.

code

function findKthLargest(nums: number[], k: number) :number {
    return nums.sort((a, b) = >b - a)? .[k -1];
};
Copy the code

Fast row

Use the idea of fast sorting to find the KTH largest value

Train of thought

Quick row basic idea:

  1. Random array[i, j]A reference value in, let’s sayqIs the index of the benchmark value;
  2. Then thanqThe large value moves topTo the right, will beqSmall values move topTo the left of, such an array[i, j]It will beqDivided into left and right sections[i, q - 1]and[i, q + 1];
  3. And then we recursively do the same thing on both intervals, and we get sorted.

This is where q gets sorted, because the goal is to find the KTH largest value, and as long as it happens to be the KTH largest value, you just return it, and you don’t have to judge, you don’t have to sort the whole array.

So there’s an optimization point here, so let’s figure out where Q and K are, if Q is to the left of K, we just recurse over the left interval, anyway, over the right interval

code

function findKthLargest(nums: number[], k: number) :number {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
};

function quickSelect(nums: number[], l: number, r: number, index: number) :number {
    const q = partition(nums, l, r);
    if (q === index) {
        // Find the target value, return
        return nums[q];
    } else {
        return q < index ?
            quickSelect(nums, q + 1, r, index) : // recurse the left interval
            quickSelect(nums, l, q - 1, index); // Recurse the right range}}function partition(nums: number[], l: number, r: number) :number {
    let x = nums[r]; // Take the last term as the reference point, greater than it put it to the right, less than it put it to the left
    let i = l - 1; // The last position of the datum
    for (let j = l; j < r; j++) {
        // If the current value is less than the datum, swap
        if (nums[j] <= x) {
            swap(nums, ++i, j); // I + 1 to ensure that I is the last value less than the base value
        }
    }
    swap(nums, ++i, r); // I + 1 becomes the first position greater than the base value, and then swaps the first position greater than the base value and the base value
    return i; // The last I is the base position
}

/** * switch two numbers */
function swap(nums: number[], i: number, j: number) :void {
    [nums[i], nums[j]] = [nums[j], nums[i]];
}
Copy the code

Code optimization

Question:

If you take the same place every time as the base value (this is the last value of the interval), sometimes you get an extreme case where you recurse all the way to the left or all the way to the right, which is the worst case, O(n^2).

Solutions:

We can speed this up by introducing randomization, where the base value is picked randomly every time, and its time complexity is reduced to O(n).

function findKthLargest(nums: number[], k: number): number {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
};

function quickSelect(nums: number[], l: number, r: number, index: number): number {
- const q = partition(nums, l, r);
+ const q = randomPartition(nums, l, r);
    if (q === index) {// return nums[q]; } else { return q < index ? QuickSelect (nums, q + 1, r, index); Function partition(nums: number[], l: number, r: number): number {let x = nums[r];} function partition(nums: number[], l: number, r: number): number {let x = nums[r]; Let I = l - 1; let I = l - 1; For (let j = l; j < r; J++) {/ / the current value is less than the benchmark, the exchange of the if (nums [j] < = {x) swap (nums, + + I, j); }} swap(nums, ++ I, r); Return I; return I; return I; Function swap(nums: number[], I: number, j: number): void { [nums[i], nums[j]] = [nums[j], nums[i]]; }+ function randomPartition(nums: number[], l: number, r: number): number {
+ const i = getRandom(l, r); // Get random values in the range
+ swap(nums, i, r); // Swap with the last term
+ return partition(nums, l, r);
+}

+ / * *
+ * Gets a random number within a specified range
+  */
+ function getRandom(n: number, m: number): number {
+ return Math.floor(Math.random() * (m - n + 1) + n)
+}
Copy the code

Heap sort

Train of thought

What we want is the KTH largest element, so we only sort some elements, not the whole array.

The heap is a complete binary tree, so it can be mapped using arrays.

  • The firstnThe left child node of the element is2 * n + 1
  • The firstnThe right child node of the element is2 * n + 2
  • The firstnThe parent node of the element isMath.floor((n - 1) / 2)
  • The last non-leaf node isMath.floor(arr.length / 2) - 1

Heap sort is an algorithm based on heap data structure.

There are two types of heap:

  • Big top heap: Each node has a value greater than or equal to the value of its left and right children
  • Small top heap: Each node has a value less than or equal to the value of its left and right children

There is no size requirement for the two children of a node

I’m looking for the KTH largest element here, so it’s obvious to use the big top heap.

Heap sort is to sort some elements, using heap sort can traverse the unordered array has a certain rule of the big top heap array. The root element of the large top heap, that is, the first item of the array must be the largest, delete the largest and reorder, move the second largest to the top of the heap, delete k-1 times, then obtain the KTH largest element.

How to turn disorderly array into big top pile of reference articles: www.cnblogs.com/chengxiao/p…

code

function findKthLargest(nums: number[], k: number) :number {
    let { length } = nums;

    buildMaxHeap(nums, length); // Build the array as a big top heap

    // find the KTH element
    for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
        swap(nums, 0, i); // Place the top element (the largest one) at the end of the array
        length--; // Heap top elements no longer float up after parameters
        // Float up subsequent maximums
        bubble(nums, 0, length);
    }

    return nums[0];
};

function buildMaxHeap(nums: number[], length: number) {
    for (let i = Math.floor(length / 2); i >= 0; i--) {
        bubble(nums, i, length); // Float up}}/** * float */
function bubble(nums: number[], i: number, length: number) {
    const l = i * 2 + 1; // Left child node
    const r = i * 2 + 2; // Right child node
    let largest = i; // Maximum subscript

    // Compare the size of the current node with its two children
    if (l < length && nums[l] > nums[largest]) {
        largest = l;
    }
    if (r < length && nums[r] > nums[largest]) {
        largest = r;
    }
    
    // If the current value is not the maximum
    if(largest ! == i) {/ / to rise
        swap(nums, i, largest);
        // Continue to adjust the child nodes belowbubble(nums, largest, length); }}/** * switch two numbers */
function swap(nums: number[], i: number, j: number) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
}
Copy the code