This is question of the Day from LeetCode 2021-9-3: “Interview Question 17.14. Minimum K number.”

1. Topic description

Design an algorithm to find the smallest k number in an array. You can return these k numbers in any order.

Example:

Arr = [1,3,5,7,2,4,6,8], k = 4 output: [1,2,3,4]Copy the code

2. Answer

1. Sort

Sort + returns the first k number.

const smallestK = (arr, k) = > {
    arr.sort((a, b) = > a - b);
    arr.length = k;
    return arr;
};
Copy the code

2. The heap sort

Puts the number of array arr into the minimum heap, and returns the first k number in the heap.

// Default maximum heap
const defaultCmp = (x, y) = > x > y;
// Swap elements
const swap = (arr, i, j) = > ([arr[i], arr[j]] = [arr[j], arr[i]]);
// Heap class, default maximum heap
class Heap {
    constructor(cmp = defaultCmp) {
        this.container = [];
        this.cmp = cmp;
    }
    / / insert
    insert(data) {
        const { container, cmp } = this;
        container.push(data);
        let index = this.size() - 1;
        while (index) {
            let parent = (index - 1) > >1;
            if(! cmp(container[index], container[parent])) {return; } swap(container, index, parent); index = parent; }}// Pop the top of the heap and return
    pop() {
        const { container, cmp } = this;
        if (!this.size()) {
            return null;
        }

        swap(container, 0.this.size() - 1);
        const res = container.pop();
        const length = this.size();
        let index = 0,
            exchange = index * 2 + 1;

        while (exchange < length) {
            // // In the case of the largest heap: if there is a right node and the value of the right node is greater than the value of the left node
            let right = index * 2 + 2;
            if (right < length && cmp(container[right], container[exchange])) {
                exchange = right;
            }
            if(! cmp(container[exchange], container[index])) {break;
            }
            swap(container, exchange, index);
            index = exchange;
            exchange = index * 2 + 1;
        }

        return res;
    }
    // Get the heap size
    size() {
        return this.container.length;
    }
    // Get the heap top
    peek() {
        if (this.size()) return this.container[0];
        return null; }}const smallestK = (arr, k) = > {
    const minHeap = new Heap((x, y) = > x < y);
    for (const num of arr) {
        minHeap.insert(num);
    }
    const res = [];
    for (let i = 0; i < k; i++) {
        res.push(minHeap.pop());
    }
    return res;
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”