This is the 16th day of my participation in the August Text Challenge.More challenges in August

Hello, everyone! Today, I will share with you the next simple and difficult topic of LeetCode [reference to Offer 40. The minimum number of K](leetcode-cn.com/problems/gr…).

The title

Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.

Example 1: input: arr = [3,2,1], k = 2 output: [1,2] or [2,1] example 2: input: arr = [0,1,2,1], k = 1 output: [0]Copy the code

Analysis of the

1. Integer arrays

2. There are duplicate values

3. A negative number

4. Output the smallest k array

solution

1.sort

2.maxHeap

Solution a:sort

Train of thought1.After sorting one-way increment2.Take the smallest first k number */var getLeastNumbers = function (arr, k) {
  return arr.sort((a, b) = > a - b).slice(0, k);
};

/* Complexity time O(logn) space O(logn) */
Copy the code

Method 2:maxHeap

Train of thought1.The class that writes the largest stack2.Use maximum stack to store all elements3.Extract arr. Len-k elements4.Return the remaining element is the smallest element */// maxHeap is used as a reference https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/chao-quan-3chong-jie-fa-zhi-jie-pai-xu-zui-da-dui-/

// Swap elements
function swap(arr, i, j) {
  const temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}

class MaxHeap {
  constructor(arr) {
    this.array = [];
    if (Array.isArray(arr)) {
      // Make the input arR into the maximum heap
      for (const item of arr) {
        this.insert(item); }}}/ / insert
  insert(item) {
    // Put the element at the end first
    this.array.push(item);
    let index = this.array.length - 1;
    // Maintain the maxHeap structure to ensure that the parent is larger than the child
    this.heapifyUp(index);
  }

  heapifyUp(index) {
    // Continuously compare the parent classes, eventually forming a maximum heap of tree structure
    while (index) {
      Math.floor((index-1)/2)
      let parentIndex = Math.floor((index - 1) / 2);
      const child = this.array[index];
      const parent = this.array[parentIndex];
      // Compare elements of the parent class, and if larger, swap places with the parent class
      if (child > parent) {
        swap(this.array, index, parentIndex);
        index = parentIndex;
      } else {
        break; }}}// Delete the method
  extract() {
    if (!this.array.length) return null;
    // Replace the root element of the maxHeap with the following element
    swap(this.array, 0.this.array.length - 1);
    const res = this.array.pop();
    const index = 0;
    // Maintain the maxHeap structure, comparing down to ensure that the parent is always larger than the child
    this.heapifyDown(index);
    return res;
  }

  heapifyDown(index) {
    const length = this.array.length;

    // Find the left child of the root
    let exchange = 2 * index + 1; / / the left

    // Continue to compare with the child elements until the root element is the largest
    while (exchange < length) {
      const right = 2 * index + 2;
      // If the element on the right is larger, replace the element with the element on the right and compare
      if (right < length && this.array[exchange] < this.array[right]) {
        exchange = right;
      }

      if (this.array[exchange] <= this.array[index]) {
        break;
      }

      swap(this.array, exchange, index);
      index = exchange;
      exchange = index * 2 + 1; }}top() {
    if (this.array.length) return this.array[0];
    return null; }}var getLeastNumbers = function (arr, k) {
  // Place all elements in the heap
  const maxHeap = new MaxHeap(arr);
  / / remove the arr. Length - k
  for (let i = 0; i < arr.length - k; i++) {
    maxHeap.extract();
  }

  // What is left is the smallest number of k
  return maxHeap.array;
};

/* Complexity time O(nLogn) space O(n) */
Copy the code

conclusion

The maxHeap root is the maximum value in the maxHeap, and sort is also a common method of selecting the minimum range

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]