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

实行结果:通过
实行用时和内存消耗如下：
 

 

 

1. // 最小堆的节点结构体
2. typedef struct {
3.     long long* heap;
4.     int size;
5.     int capacity;
6. } MinHeap;
8. // 初始化最小堆
9. MinHeap* createMinHeap(int capacity) {
10.     MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
11.     minHeap->size = 0;
12.     minHeap->capacity = capacity;
13.     minHeap->heap = (long long*)malloc(capacity * sizeof(long long));
14.     return minHeap;
15. }
17. // 插入元素到最小堆
18. void insert(MinHeap* minHeap, long long value) {
19.     if (minHeap->size == minHeap->capacity) {
20.         return; // 堆已满
21.     }
22.     int i = minHeap->size++;
23.     while (i != 0 && value < minHeap->heap[(i - 1) / 2]) {
24.         minHeap->heap[i] = minHeap->heap[(i - 1) / 2];
25.         i = (i - 1) / 2;
26.     }
27.     minHeap->heap[i] = value;
28. }
30. // 移除并返回最小堆的最小元素
31. long long extractMin(MinHeap* minHeap) {
32.     if (minHeap->size <= 0) {
33.         return -1;
34.     }
35.     if (minHeap->size == 1) {
36.         minHeap->size--;
37.         return minHeap->heap[0];
38.     }
39.     long long root = minHeap->heap[0];
40.     minHeap->heap[0] = minHeap->heap[--minHeap->size];
41.     int i = 0;
42.     while (2 * i + 1 < minHeap->size) {
43.         int leftChild = 2 * i + 1;
44.         int rightChild = 2 * i + 2;
45.         int smallest = i;
46.         if (leftChild < minHeap->size && minHeap->heap[leftChild] < minHeap->heap[smallest]) {
47.             smallest = leftChild;
48.         }
49.         if (rightChild < minHeap->size && minHeap->heap[rightChild] < minHeap->heap[smallest]) {
50.             smallest = rightChild;
51.         }
52.         if (smallest != i) {
53.             long long temp = minHeap->heap[smallest];
54.             minHeap->heap[smallest] = minHeap->heap[i];
55.             minHeap->heap[i] = temp;
56.             i = smallest;
57.         } else {
58.             break;
59.         }
60.     }
61.     return root;
62. }
64. // 释放最小堆内存
65. void freeMinHeap(MinHeap* minHeap) {
66.     free(minHeap->heap);
67.     free(minHeap);
68. }
70. int minOperations(int* nums, int numsSize, int k) {
71.     MinHeap* minHeap = createMinHeap(numsSize);
72.     for (int i = 0; i < numsSize; ++i) {
73.         insert(minHeap, nums[i]);
74.     }
76.     int operations = 0;
77.     while (minHeap->size >= 2 && minHeap->heap[0] < k) {
78.         long long x = extractMin(minHeap);
79.         long long y = extractMin(minHeap);
80.         long long newValue = x * 2 + y;
81.         insert(minHeap, newValue);
82.         ++operations;
83.     }
85.     freeMinHeap(minHeap);
86.     return operations;
87. }

复制代码

解题思绪：
这段代码实现了一个最小堆数据结构，并使用它来办理一个特定的题目：给定一个整数数组 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企服之家，中国第一个企服评测及商务社交产业平台。