剑指 Offer 40. 最小的k个数

[Geekhyt]

原题链接

数组 sort 排序

const getLeastNumbers = function(arr, k) {
    return arr.sort((a, b) => a - b).slice(0, k)
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(logn)

大顶堆

我们可以借助大顶堆，因为大顶堆的节点值都大于等于其左右子节点的值，并且堆顶的元素最大。

JavaScript 需要自己构建大顶堆，可以参考：https://juejin.cn/post/6932482325159067656

1. 从数组中取出前 k 个数，构建一个大顶堆
2. 从 k 开始遍历数组，每个元素都与堆顶元素比较，如果比堆顶元素小，则将其替换为堆顶元素，然后再堆化成一个大顶堆
3. 这样遍历完成后，堆中的数据就是前 K 小的元素了

const getLeastNumbers = function(arr, k) {
    const heap = [,]
    let i = 0
    while (i < k) {
       heap.push(arr[i++]) 
    }
    buildHeap(heap, k)
    for (let i = k; i < arr.length; i++) {
        if (heap[1] > arr[i]) {
            heap[1] = arr[i]
            heapify(heap, k, 1)
        }
    }
    heap.shift()
    return heap
}


const buildHeap = (arr, k) => {
    if (k === 1) return
    for (let i = Math.floor(k / 2); i >= 1 ; i--) {
        heapify(arr, k, i)
    }
}

const heapify = (arr, k, i) => {
    while (true) {
        let maxIndex = i
        if (2 * i <= k && arr[i] < arr[2 * i]) {
            maxIndex = 2*i
        }
        if (2 * i + 1 <= k && arr[maxIndex] < arr[2 * i + 1]) {
            maxIndex = 2 * i + 1
        }
        if (maxIndex !== i) {
            swap(arr, i, maxIndex)
            i = maxIndex
        } else {
            break
        }
    }
}

const swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

• 时间复杂度: O(nlogk)
• 空间复杂度: O(k)

计数排序

数组范围有限时，要想到用计数排序。

用一个新的数组统计每个数字出现的次数，然后控制输出前 k 个即可。

const getLeastNumbers = function(arr, k) {
    const countingSort = (arr, maxValue, k) => {
        const len = arr.length
        const bucket = new Array(maxValue + 1)
        const bucketLen = maxValue + 1
        let sortedIndex = 0

        for (let i = 0; i < len; i++) {
            if (!bucket[arr[i]]) {
                bucket[arr[i]] = 0
            }
            bucket[arr[i]]++
        }

        const res = []
        for (let j = 0; j < bucketLen; j++) {
            while (bucket[j]-- > 0 && sortedIndex < k) {
                res[sortedIndex++] = j
            }
            if (sortedIndex === k) {
                break
            }
        }
        return res
    }
    return countingSort(arr, 10000, k)
}

• 时间复杂度: O(n + m)，m 表示数据范围
• 空间复杂度: O(k + m)