Leecode刷题C语言之超过阈值的最小操作数②
实行结果:通过实行用时和内存消耗如下：
https://i-blog.csdnimg.cn/direct/ddea679a558349af9c50ba42e5d3d581.png
https://i-blog.csdnimg.cn/direct/9e98ca39f83340a492c3518b92ccbc87.png
https://i-blog.csdnimg.cn/direct/59fff641d43f411fa4998843bb12463f.png
// 最小堆的节点结构体
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 = minHeap->heap[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->heap = value;
}
// 移除并返回最小堆的最小元素
long long extractMin(MinHeap* minHeap) {
if (minHeap->size <= 0) {
return -1;
}
if (minHeap->size == 1) {
minHeap->size--;
return minHeap->heap;
}
long long root = minHeap->heap;
minHeap->heap = 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 < minHeap->heap) {
smallest = leftChild;
}
if (rightChild < minHeap->size && minHeap->heap < minHeap->heap) {
smallest = rightChild;
}
if (smallest != i) {
long long temp = minHeap->heap;
minHeap->heap = minHeap->heap;
minHeap->heap = 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);
}
int operations = 0;
while (minHeap->size >= 2 && minHeap->heap < 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。
这种方法使用了最小堆的性子，确保了每次操作都能有用地处理当前最小的元素，从而以尽可能少的操作次数到达目标值 k。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]