Leecode刷题C语言之超过阈值的最小操作数②

执行结果:通过

执行用时和内存消耗如下：

// 最小堆的节点结构体
typedef struct {
    long long* heap;
    int size;
    int capacity;
} MinHeap;

// 初始化最小堆
MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->heap = (long long*)malloc(capacity * sizeof(long long));
    return minHeap;
}

// 插入元素到最小堆
void insert(MinHeap* minHeap, long long value) {
    if (minHeap->size == minHeap->capacity) {
        return; // 堆已满
    }
    int i = minHeap->size++;
    while (i != 0 && value < minHeap->heap[(i - 1) / 2]) {
        minHeap->heap[i] = minHeap->heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->heap[i] = value;
}

// 移除并返回最小堆的最小元素
long long extractMin(MinHeap* minHeap) {
    if (minHeap->size <= 0) {
        return -1;
    }
    if (minHeap->size == 1) {
        minHeap->size--;
        return minHeap->heap[0];
    }
    long long root = minHeap->heap[0];
    minHeap->heap[0] = minHeap->heap[--minHeap->size];
    int i = 0;
    while (2 * i + 1 < minHeap->size) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int smallest = i;
        if (leftChild < minHeap->size && minHeap->heap[leftChild] < minHeap->heap[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < minHeap->size && minHeap->heap[rightChild] < minHeap->heap[smallest]) {
            smallest = rightChild;
        }
        if (smallest != i) {
            long long temp = minHeap->heap[smallest];
            minHeap->heap[smallest] = minHeap->heap[i];
            minHeap->heap[i] = temp;
            i = smallest;
        } else {
            break;
        }
    }
    return root;
}

// 释放最小堆内存
void freeMinHeap(MinHeap* minHeap) {
    free(minHeap->heap);
    free(minHeap);
}

int minOperations(int* nums, int numsSize, int k) {
    MinHeap* minHeap = createMinHeap(numsSize);
    for (int i = 0; i < numsSize; ++i) {
        insert(minHeap, nums[i]);
    }

    int operations = 0;
    while (minHeap->size >= 2 && minHeap->heap[0] < k) {
        long long x = extractMin(minHeap);
        long long y = extractMin(minHeap);
        long long newValue = x * 2 + y;
        insert(minHeap, newValue);
        ++operations;
    }

    freeMinHeap(minHeap);
    return operations;
}

解题思路：

这段代码实现了一个最小堆数据结构，并利用它来解决一个特定的问题：给定一个整数数组 nums 和一个整数 k，计算将数组中的元素通过一系列操作转换成大于或等于 k 的最小元素所需的最少操作次数。每次操作可以取出堆中的两个最小元素，将它们相加后乘以2，再将结果放回堆中。

下面是代码的解题思路：

定义最小堆结构体：
- MinHeap 结构体包含三个成员：指向堆数组的指针 heap，堆的当前大小 size，以及堆的容量 capacity。
初始化最小堆：
- createMinHeap 函数分配内存并初始化一个最小堆，设置堆的大小为0，并分配足够的空间来存储指定容量的元素。
插入元素到最小堆：
- insert 函数将一个新元素添加到最小堆中。如果堆未满，它首先将元素添加到堆的末尾，然后通过上滤（bubble up）操作将其移动到正确的位置，以保持堆的性质。
移除并返回最小元素：
- extractMin 函数移除并返回堆中的最小元素（根元素）。它首先将根元素替换为堆中的最后一个元素，然后通过下滤（bubble down）操作将新的根元素移动到正确的位置。
释放最小堆内存：
- freeMinHeap 函数释放最小堆所占用的内存。
计算最少操作次数：
- minOperations 函数是解决问题的核心。它首先创建一个最小堆，并将数组 nums 中的所有元素插入堆中。
- 然后，它进入一个循环，只要堆的大小至少为2且堆顶元素（最小元素）小于 k，就执行以下操作：
  - 从堆中取出两个最小元素 x 和 y。
  - 计算新值 newValue = x * 2 + y。
  - 将 newValue 插入堆中。
  - 操作次数 operations 加1。
- 循环结束后，释放堆的内存，并返回操作次数 operations。