题解 | #最小的K个数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param input int整型一维数组 
 * @param inputLen int input数组长度
 * @param k int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

#include <stdio.h>
#include <stdlib.h>

// 交换两个整数的函数
void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

// 大顶堆的调整函数，用于维护大顶堆的性质
void maxHeapify(int* input, int i, int heapSize) {
    int left = 2 * i + 1; // 左子树索引
    int right = 2 * i + 2; // 右子树索引
    int largest = i;
    // 比较左子节点和当前节点，找到较大值的索引
    if(left < heapSize && input[left] > input[largest]) {
        largest = left;
    }
    if(right < heapSize && input[right] > input[largest]) {
        largest = right;
    }
    // 如果最大值不是当前节点，进行交换并继续调整堆
    if(largest != i) {
        swap(&input[i], &input[largest]);
        maxHeapify(input, largest, heapSize);
    }
}

void buildMaxHeap(int* input, int heapSize) {
    for(int i = heapSize / 2 - 1; i >= 0; i--) {
        maxHeapify(input, i, heapSize);
    }
}

int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    int* result = (int*)malloc(k * sizeof(int));
    if(k == 0 || inputLen == 0) {
        *returnSize = 0;
        return result;
    }
    // 先构建一个包含数组前k个元素的大顶堆
    buildMaxHeap(input, k);
    // 遍历剩余的元素
    for(int i = k; i < inputLen; i++) {
        // 如果当前元素小于堆顶元素，将堆顶元素替换为当前元素，并调整堆
        if(input[i] < input[0]) {
            input[0] = input[i];
            maxHeapify(input, 0, k);
        }
    }

    for(int i = 0; i < k; i++) {
        result[i] = input[i];
    }
    *returnSize = k;
    return result;
}