The KTH largest element in the array

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

Description:

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

/* * @lc app=leetcode.cn id=215 lang=javascript * * the KTH largest element in the array [215] */
/** * @param {number[]} nums * @param {number} k * @return {number} */
var findKthLargest = function(nums, k) {};Copy the code

1 all sorts

This is probably the easiest way to think about it

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

Time complexity:

Space complexity:

But obviously, that’s not a good idea, so let’s say the array is 1W, and we just take the third one, and that’s embarrassing

2 part sorting (bubbling)

So, we’re thinking, just sort the first k numbers

var findKthLargest = function (nums, k) {
  for (let i = 0; i < k; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1])
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
    }
  }
  return nums[nums.length - k]
};
Copy the code

So the time complexity is zero

3 part sort (heap)

If we want the KTH element, we don’t have to sort the first k elements

At this point, a lot of people think, right? How do we know who the KTH is if we don’t know what the first k numbers are?

That brings us to the concept of a heap. If we create a minimum heap of k elements, the heap must be smaller than any element in the heap

var findKthLargest = function (nums, k) {
  let minHeap = new MinHeap()
  for (let i = 0; i < nums.length; i++) {
    if (minHeap.size() < k) minHeap.push(nums[i])
    else if (minHeap.top() < nums[i]) {
      minHeap.pop()
      minHeap.push(nums[i])
    }
  }
  return minHeap.top()
};
Copy the code

So the time complexity can be reducedBut using the heap structure gives you a certain amount of extra space, and the space complexity is

Of course, the heap structure here has to be implemented by itself

If you don’t know how to write it you can look at my heap and heap sort

class MinHeap {
  constructor() {
    this.heap = []
    this.len = 0
  }
  size() {
    return this.len
  }
  push(val) {
    this.heap[++this.len] = val
    this.swin(this.len)
  }

  pop() {
    const ret = this.heap[1]
    this.swap(1.this.len--)
    this.heap[this.len + 1] = null
    this.sink(1)
    return ret
  }
  swin(ind) {
    while (ind > 1 && this.less(ind, parseInt(ind / 2))) {
      this.swap(ind, parseInt(ind / 2))
      ind = parseInt(ind / 2)
    }
  }
  sink(ind) {
    while (ind * 2< =this.len) {
      let j = ind * 2
      if (j < this.len && this.less(j + 1, j)) j++
      if (this.less(ind, j)) break
      this.swap(ind, j)
      ind = j
    }
  }
  top() {
    return this.heap[1]
  }
  isEmpty() {
    return this.len === 0
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
  }
  less(i, j) {
    return this.heap[i] < this.heap[j]
  }
}
Copy the code

4 Quick Selection

In fact, when faced with a problem to find a certain element that matches, that is, the search problem

Binary search often comes to mind immediately

function binarySearch(arr, val) {
  let low = 0
  let high = arr.length - 1
  while (low <= high) {
    // mid indicates the middle value
    let mid = Math.floor(low + (high - low) / 2)
    if (arr[mid] === val) return mid
    val < arr[mid] ? high = mid - 1 : low = mid + 1
  }
  return null
}

let arr = [0.1.2.3.4.5]
console.log(binarySearch(arr, 0));
Copy the code

Binary search is based on the premise that arr[mid] is a median value so that the other half can be excluded

With the median, we have to think of quicksort Pivot

The partition function is a perfect match for binary lookup

function quickSort(arr) {
  return quick(arr, 0, arr.length - 1)}function quick(arr, left, right) {
  if (arr.length > 1) {
    let index = partition(arr, left, right)
    if (left < index - 1) quick(arr, left, index - 1)
    if (index < right) quick(arr, index, right)
  }
  return arr
}
function partition(arr, left, right) {
  const pivot = arr[Math.floor(left + (right - left) / 2)]
  let i = left
  let j = right
  while (i <= j) {
    while (arr[i] < pivot) i++
    while (pivot < arr[j]) j--
    if(i <= j) { [arr[i], arr[j]] = [arr[j], arr[i]] i++; j--; }}return i
}
let arr = [11.2.33.4.5]
console.log(quickSort(arr));
Copy the code

If you don’t understand quicksort, you can read my sort evolution (3) : Fast

But this way the pivot will be in the left array, not between right and left

So what we need to do is change the partition so that the pivot value comes out

function partition(arr, left, right) {
  let mid = Math.floor(left + (right - left) / 2)
  const pivot = arr[mid]
  // Place pivot at the end of arR
  [arr[mid], arr[right]] = [arr[right], arr[mid]]
  let i = left
  // Exclude pivot and do not sort pivot
  let j = right - 1
  while (i <= j) {
    while (arr[i] < pivot) i++
    while (pivot < arr[j]) j--
    if(i <= j) { [arr[i], arr[j]] = [arr[j], arr[i]] i++; j--; }}// Since arr[I] belongs to the left,pivot also belongs to the left
  // So we can swap the protected pivot with the middle value of the current array
  [arr[right], arr[i]] = [arr[i], arr[right]]
  return i
}
Copy the code

Now we just need to add the partition above in the binary search can achieve fast search

But the main thing is, do we want ascending or descending?

We’re looking for the KTH largest element

So the order of the array should be

Arr = [5,4,3,2,1]

For example, in the array above, the second largest number is 4, arr[1]

Our partition should be in reverse order, so the above code should be changed to

while (i <= j) {
+ while (arr[i] > pivot) i++
- while (arr[i] < pivot) i++
+ while (pivot < arr[j]) j--
- while (pivot < arr[j]) j--if (i <= j) { [arr[i], arr[j]] = [arr[j], arr[i]] i++; j--; }}Copy the code

Arr [I] is the k-1 bit of the partition, because the subscript is 0 and the first bit is I === 0

while (low <= high) {
  const mid = partition(arr.low, high)
  if (mid === k - 1) return arr[mid]

}
Copy the code

Arr [mid+1]~arr[high] if mid < k -1, arr[mid+1]~arr[high

Arr [low] ~ arr[mid – 1] arr[mid] ~ arr[mid – 1

So the code is

while (low <= high) {
  const mid = partition(nums, low, high)
  if (mid === k - 1) return nums[mid]
  mid < k - 1 ? low = mid + 1 : high = mid - 1
}
Copy the code

The final code is

/* * @lc app=leetcode.cn id=215 lang=javascript * * the KTH largest element in the array [215] */
/** * @param {number[]} nums * @param {number} k * @return {number} */
var findKthLargest = function (nums, k) {
  let low = 0
  let high = nums.length - 1
  while (low <= high) {
    const mid = partition(nums, low, high)
    if (mid === k - 1) return nums[mid]
    mid < k - 1 ? low = mid + 1 : high = mid - 1}}function partition(arr, low, high) {
  let mid = Math.floor(low + (high - low) / 2)
  const pivot = arr[mid]; // Remember to add a semicolon here
  // Place pivot at the end of arR
  [arr[mid], arr[high]] = [arr[high], arr[mid]]
  let i = low
  // Exclude pivot and do not sort pivot
  let j = high - 1
  while (i <= j) {
    while (arr[i] > pivot) i++
    while (arr[j] < pivot) j--
    if(i <= j) { [arr[i], arr[j]] = [arr[j], arr[i]] i++; j--; }}// Since arr[I] belongs to the left,pivot also belongs to the left
  // So we can swap the protected pivot with the middle value of the current array
  [arr[high], arr[i]] = [arr[i], arr[high]]
  return i
}
Copy the code

Complexity analysis

• Time complexity: averageWorst-case scenario
• Space complexity: