给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。 数据范围：0≤k,n≤100000≤k,n≤10000，数组中每个数的大小0≤val≤10000≤val≤1000 要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogk)O(nlogk) ，用c语言编程，动态存储

可以使用堆来解决这个问题，具体步骤如下：

1. 建立一个大小为 k 的最大堆（大根堆），堆中存放数组中前 k 个数。

2. 遍历数组中剩余的数（从第 k+1 个数开始），如果该数比堆顶元素小，则将堆顶元素出堆，将该数加入堆中；否则不做处理。

3. 遍历完数组后，堆中剩下的 k 个数就是不去重的最小的 k 个数。

C语言代码实现如下：

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

typedef struct {
    int *data;  // 堆的数组
    int size;   // 堆的大小
    int count;  // 堆中元素个数
} Heap;

// 初始化堆
Heap* init_heap(int size) {
    Heap *h = (Heap*) malloc(sizeof(Heap));
    h->data = (int*) malloc(sizeof(int) * (size + 1));  // 数组下标从1开始
    h->size = size;
    h->count = 0;
    return h;
}

// 插入元素
void insert(Heap *h, int val) {
    if (h->count == h->size) return;  // 堆满了
    h->count++;
    h->data[h->count] = val;  // 插入到最后一个位置
    // 自下往上堆化
    int i = h->count;
    while (i / 2 > 0 && h->data[i] > h->data[i / 2]) {
        int tmp = h->data[i];
        h->data[i] = h->data[i / 2];
        h->data[i / 2] = tmp;
        i /= 2;
    }
}

// 删除堆顶元素
void remove_max(Heap *h) {
    if (h->count == 0) return;  // 堆空了
    h->data[1] = h->data[h->count];  // 最后一个元素移到堆顶
    h->count--;
    // 自上往下堆化
    int i = 1;
    while (i * 2 <= h->count) {
        int j = i * 2;
        if (j + 1 <= h->count && h->data[j + 1] > h->data[j]) j++;
        if (h->data[i] >= h->data[j]) break;
        int tmp = h->data[i];
        h->data[i] = h->data[j];
        h->data[j] = tmp;
        i = j;
    }
}

// 获取堆顶元素
int get_max(Heap *h) {
    if (h->count == 0) return -1;  // 堆空了
    return h->data[1];
}

// 释放堆
void free_heap(Heap *h) {
    free(h->data);
    free(h);
}

// 打印堆中的元素（调试用）
void print_heap(Heap *h) {
    for (int i = 1; i <= h->count; i++) {
        printf("%d ", h->data[i]);
    }
    printf("\n");
}

// 找出不去重的最小的 k 个数
void find_k_min(int *a, int n, int k) {
    Heap *h = init_heap(k);
    // 插入前 k 个数
    for (int i = 0; i < k; i++) {
        insert(h, a[i]);
    }
    // 遍历剩余的数
    for (int i = k; i < n; i++) {
        if (a[i] < get_max(h)) {
            remove_max(h);
            insert(h, a[i]);
        }
    }
    // 输出结果
    for (int i = 1; i <= k; i++) {
        printf("%d ", h->data[i]);
    }
    printf("\n");
    free_heap(h);
}

int main() {
    int a[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int n = sizeof(a) / sizeof(int);
    int k = 4;
    find_k_min(a, n, k);
    return 0;
}