企业请别人做网站,wordpress上一篇下一篇箭头,wordpress 顶 踩,万网速成网站有哪些 功能目录 常见思路更优的解法#xff08;面试官喜欢的#xff09; 常见思路 要选出最小的前K个数首先我们会想到排排升序建大堆#xff0c;排降序建小堆 一个直观的想法是使用#xff08;小根堆#xff09;#xff0c;起始将所有元素放入堆中#xff0c;然后再从堆中取出k 个… 目录 常见思路更优的解法面试官喜欢的 常见思路 要选出最小的前K个数首先我们会想到排排升序建大堆排降序建小堆 一个直观的想法是使用小根堆起始将所有元素放入堆中然后再从堆中取出k 个元素并「顺序」构造答案。你写出了用小堆解决的代码 void swap(int* a, int* b) {int t *a;*a *b;*b t;
}void minHeapify(int arr[], int n, int i) {int smallest i;int left 2 * i 1;int right 2 * i 2; if (left n arr[left] arr[smallest])smallest left;if (right n arr[right] arr[smallest])smallest right;if (smallest ! i) {swap(arr[i], arr[smallest]);minHeapify(arr, n, smallest);}
}void buildMinHeap(int arr[], int n) {// Index of last non-leaf nodeint startIdx (n / 2) - 1;for (int i startIdx; i 0; i--)minHeapify(arr, n, i);
}int extractMin(int arr[], int* n) {if (*n 0)return INT_MAX;if (*n 1) {(*n)--;return arr[0];}int root arr[0];arr[0] arr[*n - 1];(*n)--;minHeapify(arr, *n, 0);return root;
}void findKSmallest(int arr[], int n, int k) {buildMinHeap(arr, n);printf(The k smallest elements are: );for (int i 0; i k; i) {printf(%d , extractMin(arr, n));}printf(\n);
} 分析一下不难发现 建堆的复杂度是 ON 每次提取的复杂度是 O(logN) 总的复杂度ONlogN 面试官看到你的代码后并不满意并要求你进行优化 更优的解法面试官喜欢的 使用大根堆! 当处理到原始 arr[i] 时根据堆内元素个数以及其与堆顶元素的关系分情况讨论 堆内元素不足 k 个直接将 arr[i] 放入堆内 堆内元素为 k 个根据 arr[i] 与堆顶元素的大小关系分情况讨论 arr[i]heapToparr[i] 不可能属于第 k 小数已有 k 个元素在堆中直接丢弃 arr[i] arr[i]heapToparr[i] 可能属于第 k 小数弹出堆顶元素并放入 arr[i]。 你出写了如下代码。
void swap(int* a, int* b) {int t *a;*a *b;*b t;
}void maxHeapify(int arr[], int n, int i) {int largest i;int left 2 * i 1;int right 2 * i 2; // 如果左子节点大于当前节点则更新最大值索引if (left n arr[left] arr[largest])largest left;// 如果右子节点大于当前节点则更新最大值索引if (right n arr[right] arr[largest])largest right;// 如果最大值索引不是当前节点则交换并递归调整子树if (largest ! i) {swap(arr[i], arr[largest]);maxHeapify(arr, n, largest);}
}void buildMaxHeap(int arr[], int n) {// 最后一个非叶子节点的索引int startIdx (n / 2) - 1;// 从最后一个非叶子节点开始逆序遍历并调整每个节点for (int i startIdx; i 0; i--)maxHeapify(arr, n, i);
}// 提取堆顶元素并调整堆的函数
int extractMax(int arr[], int* n) {if (*n 0)return INT_MAX; // 堆为空时返回最大整数值if (*n 1) {(*n)--;return arr[0]; // 堆只有一个元素时直接返回}// 存储并移除堆顶元素int root arr[0];arr[0] arr[*n - 1];(*n)--;maxHeapify(arr, *n, 0); // 调整堆以保持大根堆性质return root;
}void findKSmallest(int arr[], int n, int k) {// 构建包含前k个元素的大根堆int heap[k];for (int i 0; i k; i) {heap[i] arr[i];}buildMaxHeap(heap, k);// 遍历剩余元素for (int i k; i n; i) {// 如果当前元素小于堆顶元素则替换堆顶元素并重新调整堆if (arr[i] heap[0]) {heap[0] arr[i];maxHeapify(heap, k, 0);}}
} 时间复杂度ONlogK当N无限大时logK可以忽略 比ONlogN更优
