讨论/《堆》 - 剑指 Offer 40. 最小的 K 个数/
《堆》 - 剑指 Offer 40. 最小的 K 个数
共 3 个回复

Python 写好短啊……

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        heapq.heapify(arr)
        return [heapq.heappop(arr) for _ in range(k)]

C语言:参考《大话数据结构》

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    int *d;
    int len;
} SqList;

void swap(SqList *L, int a, int b) {
    int t = L->d[a];
    L->d[a] = L->d[b];
    L->d[b] = t;
}

void HeapAdjust(SqList *L, int s, int m) {
    int j, t;
    t = L->d[s];
    for (j = 2 * s; j <= m; j *= 2) {
        if (j < m && L->d[j] < L->d[j + 1]) {
            ++j; // 选出更大的索引
        }
        if (t >= L->d[j]) {
            break;
        }
        L->d[s] = L->d[j];
        s = j;
    }
    L->d[s] = t;
}
void HeapSort(SqList *L) {
    int i;
    for (i = L->len / 2; i > 0; i--) {
        HeapAdjust(L, i, L->len);
    }

    // 堆排序
    for (i = L->len; i > 0; i--) {
        swap(L, 1, i);
        HeapAdjust(L, 1, i - 1);
    }
}

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
    *returnSize = k;
    if (k == 0 || k > arrSize) {
        return NULL;
    }
    int *ans = (int *)malloc(sizeof(int) * k);
    SqList L;
    L.len = arrSize;
    L.d = (int *)malloc(sizeof(int) * (arrSize + 1)); // 把0留出来
    int i;
    for (i = 0; i < arrSize; i++) {
        L.d[i + 1] = arr[i];
    }

    HeapSort(&L);

    for (i = 0; i < k; i++) {
        ans[i] = L.d[i + 1];
    }
    return ans;
}

作者:luckyBigBear
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/xi-jie-shi-mo-gui-can-kao-da-hua-shu-ju-6iplg/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> q;
        for(auto now : arr){
            q.push(now);
            if(q.size() == k + 1){
                q.pop();
            }
        }
        vector<int> result(k);
        for(int i=0;i<k;i++){
            result[i] = q.top();
            q.pop();
        }
        return result;
    }
};