最小的k个数 - Githubissues

方法1：使用API

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

时间复杂度：O(nlogn) 空间复杂度：O(logn)

方法2：使用最大堆

思路：取数组前k个数，创建最大堆。遍历数组后续的数，若数比最大堆顶的元素小，则将该数替换最大堆顶元素，调整堆再次成为最大堆，持续数组遍历和最大堆调整，直至遍历完成，最后打印出最大堆所有的元素，即为最终结果。

let getLeastNumbers = function(arr, k) {
    // 从 arr 中取出前 k 个数，构建一个大顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(arr[i++]) 
    }
    buildHeap(heap, k)

    // 从 k 位开始遍历数组
    for(let i = k; i < arr.length; i++) {
        if(heap[1] > arr[i]) {
            // 替换并堆化
            heap[1] = arr[i]
            heapify(heap, k, 1)
        }
    }

    // 删除heap中第一个元素
    heap.shift()
    return heap
};

// 原地建堆，从后往前，自上而下式建大顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}

// 堆化
let heapify = (arr, k, i) => {
    // 自上而下式堆化
    while(true) {
        let maxIndex = i
        if(2*i <= k && arr[2*i] > arr[i]) {
            maxIndex = 2*i
        }
        if(2*i+1 <= k && arr[2*i+1] > arr[maxIndex]) {
            maxIndex = 2*i+1
        }
        if(maxIndex !== i) {
            swap(arr, i, maxIndex)
            i = maxIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

时间复杂度：O(nlogk) 空间复杂度：O(k)

方法3：使用计数排序

let getLeastNumbers = function(arr, k) {
    return countingSort(arr, 10000, k)
}

let countingSort = (arr, maxValue, k) => {
    // 开辟的新的数组，用于将输入的数据值转化为键存储
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0,
        arrLen = arr.length,
        bucketLen = maxValue + 1

    // 存储
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0
        }
        bucket[arr[i]]++
    }

    // 将数据从bucket按顺序写入res中，控制仅仅输出前k个
    let res = []
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j]-- > 0 && sortedIndex < k) {
            res[sortedIndex++] = j
        }
        if(sortedIndex === k) {
            break
        }
    }
    return res
}

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

xszi / javascript-algorithms

最小的k个数 #76