广州高端网站设计,怎么做网络广告推广,自动seo网站源码,wordpress支持的视频题目描述#xff1a;
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围#xff1a;节点总数 0≤n≤50000≤n≤5000#xff0c;每个节点的val满足 ∣val∣1000∣val∣1000
要求#xff1a;时间复杂度 O(nlogn) 一、常见解法
#xff08…题目描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围节点总数 0≤n≤50000≤n≤5000每个节点的val满足 ∣val∣1000∣val∣1000
要求时间复杂度 O(nlogn) 一、常见解法
一暴力排序法
暴力排序法的思路非常直接。首先将链表数组中的所有链表进行遍历把它们头尾相接组成一个长链表。这个过程可以通过遍历链表数组对于每个链表依次将其节点添加到新的长链表中。然后对这个长链表进行排序。这种方法虽然简单易懂但是时间复杂度比较高。因为在组成长链表的过程中需要遍历整个链表数组时间复杂度为 O(k * n)其中 是链表数组的长度 n是平均每个链表的长度。而对长链表进行排序的时间复杂度取决于排序算法的选择例如快速排序的平均时间复杂度为 O(nlogn)其中 n是长链表的长度也就是所有链表长度之和。所以总体时间复杂度较高但对于一些小规模的问题或者对时间要求不高的场景这种方法仍然可以尝试。
二暴力求解优化法
暴力求解优化法是对暴力排序法的一种改进。它的核心思想是每次取出 K个链表中最小的元素不断放入结果数组中。具体实现时可以通过遍历 K个链表的首元素找到其中最小的元素将其加入结果数组然后将该最小元素所在链表的指针向后移动一位。重复这个过程直到所有链表都为空。这种方法在一定程度上减少了不必要的排序操作但是时间复杂度仍然较高。每次查找最小元素需要遍历 K个链表时间复杂度为 O(k)假设总共有 n个元素那么总体时间复杂度为 O(nk)。
三分治法
分治法是一种更加高效的方法。将 k个链表配对并将同一对中的链表合并。第一轮合并以后 k个链表被合并成了 k/2个链表平均长度为 2n/k然后是 k/4个链表k/8 个链表等等。重复这一过程直到我们得到了最终的有序链表。具体实现时可以使用递归的方式进行合并。首先将链表数组分成两部分分别对这两部分进行合并然后再将合并后的结果进行合并。这种方法的时间复杂度为 O(n log k)其中 n是所有链表的总长度k 是链表数组的长度。因为每次合并的时间复杂度为 O(n)而总共需要进行 log k次合并。
四堆排序或构建二叉排序树法
堆排序或构建二叉排序树法为解决这个问题提供了不同的思路。对于堆排序可以使用小根堆来存储链表的首元素。每次从堆中取出最小的元素将其加入结果链表然后将该元素所在链表的下一个元素加入堆中。这样可以保证每次取出的元素都是当前未处理元素中的最小值。时间复杂度为 O(n log k)其中 n是所有链表的总长度k 是链表数组的长度。对于构建二叉排序树可以将每个链表的元素依次插入二叉排序树中然后进行中序遍历得到有序链表。这种方法的时间复杂度取决于二叉排序树的构建和遍历一般情况下时间复杂度也为 O(n log k)。具体的实现可以参考相关博客中的更基础概念和示例代码。
二、代码实现
一暴力排序法
#include stdio.h
#include stdlib.h// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode-val val;// 新节点的下一个指针初始化为 NULLnewNode-next NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new createNode(val);// 如果链表为空将新节点设为链表的头节点if (*head NULL) {*head new;return;}// 临时指针指向链表的头节点struct ListNode* temp *head;// 遍历链表找到最后一个节点while (temp-next! NULL) {temp temp-next;}// 将新节点连接到链表的末尾temp-next new;
}// 合并 k 个链表暴力排序法
struct ListNode* mergeKListsBruteForce(struct ListNode** lists, int listsSize) {// 初始化结果链表为空struct ListNode* result NULL;// 遍历输入的链表数组for (int i 0; i listsSize; i) {// 获取当前链表struct ListNode* currentList lists[i];// 遍历当前链表的所有节点while (currentList! NULL) {// 将当前链表的节点值插入到结果链表中insertNode(result, currentList-val);// 移动到当前链表的下一个节点currentList currentList-next;}}// 对合并后的链表进行排序struct ListNode* current result;while (current! NULL) {// 获取当前节点的下一个节点struct ListNode* next current-next;while (next! NULL) {// 如果当前节点的值大于下一个节点的值则交换它们的值if (current-val next-val) {int temp current-val;current-val next-val;next-val temp;}// 移动到下一个节点next next-next;}// 移动到下一个节点current current-next;}return result;
}
二暴力求解优化法
#include stdio.h
#include stdlib.h// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode-val val;// 新节点的下一个指针初始化为 NULLnewNode-next NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new createNode(val);// 如果链表为空将新节点设为链表的头节点if (*head NULL) {*head new;return;}// 临时指针指向链表的头节点struct ListNode* temp *head;// 遍历链表找到最后一个节点while (temp-next! NULL) {temp temp-next;}// 将新节点连接到链表的末尾temp-next new;
}// 查找 k 个链表中的最小节点所在的链表索引
int findMinIndex(struct ListNode** lists, int listsSize) {// 初始化最小索引为 -1表示还未找到最小节点所在的链表int minIndex -1;// 初始化最小值为整数最大值int minVal __INT_MAX__;// 遍历所有链表for (int i 0; i listsSize; i) {// 如果当前链表不为空且当前链表的头节点值小于当前最小值if (lists[i]! NULL lists[i]-val minVal) {// 更新最小值minVal lists[i]-val;// 更新最小索引minIndex i;}}return minIndex;
}// 合并 k 个链表暴力求解优化法
struct ListNode* mergeKListsOptimized(struct ListNode** lists, int listsSize) {// 创建一个虚拟头节点struct ListNode* dummy createNode(0);// 当前节点指针初始指向虚拟头节点struct ListNode* current dummy;// 记录非空链表的数量int nonEmptyLists listsSize;// 当还有非空链表时循环while (nonEmptyLists 0) {// 找到 k 个链表中最小节点所在的链表索引int minIndex findMinIndex(lists, listsSize);// 如果找到了非空链表if (minIndex! -1) {// 将最小节点连接到结果链表中current-next lists[minIndex];// 当前节点指针后移current current-next;// 移动最小链表的头指针到下一个节点lists[minIndex] lists[minIndex]-next;// 如果该链表为空减少非空链表数量if (lists[minIndex] NULL) {nonEmptyLists--;}}}// 返回合并后的链表不包括虚拟头节点return dummy-next;
}
三分治法
#include stdio.h
#include stdlib.h// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode-val val;// 新节点的下一个指针初始化为 NULLnewNode-next NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new createNode(val);// 如果链表为空将新节点设为链表的头节点if (*head NULL) {*head new;return;}// 临时指针指向链表的头节点struct ListNode* temp *head;// 遍历链表找到最后一个节点while (temp-next! NULL) {temp temp-next;}// 将新节点连接到链表的末尾temp-next new;
}// 合并两个升序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {// 创建一个虚拟头节点struct ListNode dummy;// 指向虚拟头节点的指针用于构建合并后的链表struct ListNode* tail dummy;// 当两个链表都不为空时循环while (l1 l2) {// 如果第一个链表当前节点值小于第二个链表当前节点值if (l1-val l2-val) {// 将第一个链表当前节点连接到结果链表tail-next l1;// 移动第一个链表指针到下一个节点l1 l1-next;} else {// 将第二个链表当前节点连接到结果链表tail-next l2;// 移动第二个链表指针到下一个节点l2 l2-next;}// 移动结果链表指针到新连接的节点tail tail-next;}// 将剩余的非空链表连接到结果链表末尾tail-next l1? l1 : l2;// 返回合并后的链表不包括虚拟头节点return dummy.next;
}// 分治法合并 k 个链表
struct ListNode* mergeKListsDivideAndConquer(struct ListNode** lists, int start, int end) {// 如果起始索引等于结束索引说明只有一个链表直接返回该链表if (start end) {return lists[start];}// 如果起始索引大于结束索引说明没有链表可合并返回 NULLif (start end) {return NULL;}// 计算中间索引int mid start (end - start) / 2;// 递归合并左半部分链表struct ListNode* left mergeKListsDivideAndConquer(lists, start, mid);// 递归合并右半部分链表struct ListNode* right mergeKListsDivideAndConquer(lists, mid 1, end);// 合并左右两部分已合并的链表return mergeTwoLists(left, right);
}
四堆排序或构建二叉排序树法
#include stdio.h
#include stdlib.h// 链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 创建新节点
struct ListNode* createNode(int val) {// 分配内存空间给新节点struct ListNode* newNode (struct ListNode*)malloc(sizeof(struct ListNode));// 设置新节点的值newNode-val val;// 新节点的下一个指针初始化为 NULLnewNode-next NULL;return newNode;
}// 插入节点到链表尾部
void insertNode(struct ListNode** head, int val) {// 创建新节点struct ListNode* new createNode(val);// 如果链表为空将新节点设为链表的头节点if (*head NULL) {*head new;return;}// 临时指针指向链表的头节点struct ListNode* temp *head;// 遍历链表找到最后一个节点while (temp-next! NULL) {temp temp-next;}// 将新节点连接到链表的末尾temp-next new;
}// 交换两个整数的值
void swap(int* a, int* b) {// 临时变量存储其中一个整数的值int temp *a;// 将另一个整数的值赋给第一个整数*a *b;// 将临时变量的值赋给第二个整数*b temp;
}// 堆调整函数
void heapify(int arr[], int n, int i) {// 初始化当前最大元素的索引为 iint 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]);// 递归调整新的子树heapify(arr, n, largest);}
}// 构建堆
void buildHeap(int arr[], int n) {// 从最后一个非叶子节点开始调整堆for (int i n / 2 - 1; i 0; i--)heapify(arr, n, i);
}// 合并 k 个链表堆排序法
struct ListNode* mergeKListsHeap(struct ListNode** lists, int listsSize) {// 创建最小堆数组int minHeap[listsSize];int heapSize 0;// 将每个链表的第一个节点的值加入最小堆数组for (int i 0; i listsSize; i) {if (lists[i]! NULL) {minHeap[heapSize] lists[i]-val;}}// 构建最小堆buildHeap(minHeap, heapSize);// 创建虚拟头节点struct ListNode dummy;struct ListNode* tail dummy;// 当堆不为空时循环while (heapSize 0) {// 获取堆顶元素最小元素int minVal minHeap[0];// 将最小元素加入结果链表tail-next createNode(minVal);tail tail-next;// 在链表数组中找到值为最小元素的链表并将其头节点后移for (int i 0; i listsSize; i) {if (lists[i]! NULL lists[i]-val minVal) {lists[i] lists[i]-next;if (lists[i]! NULL) {// 如果该链表不为空将新的头节点值加入堆minHeap[0] lists[i]-val;} else {// 如果该链表为空用堆的最后一个元素替换堆顶元素并减小堆大小minHeap[0] minHeap[--heapSize];}// 调整堆heapify(minHeap, heapSize, 0);break;}}}// 返回合并后的链表不包括虚拟头节点return dummy.next;
}
三、总结展望
1.暴力排序法
优点思路简单直接容易理解和实现。对于小规模问题或者对时间要求不高的场景可以快速解决问题。缺点时间复杂度高特别是在处理大规模数据或者链表数量较多的情况时效率低下。
2.暴力求解优化法
优点相比暴力排序法减少了不必要的排序操作在一定程度上提高了效率。对于一些特定的输入数据可能会有较好的表现。缺点时间复杂度仍然较高每次查找最小元素需要遍历所有链表当链表数量较多时效率会受到很大影响。
3.分治法
优点时间复杂度为 相比暴力方法有很大的提升。通过递归地合并链表充分利用了链表已经升序排列的特点减少了比较次数。缺点实现相对复杂需要理解递归的思想和过程。在处理小规模问题时可能由于递归调用的开销效率不一定比其他方法高。
4.堆排序或构建二叉排序树法
优点时间复杂度为 能够快速找到当前最小的元素保证合并后的链表始终是升序的。对于大规模数据和链表数量较多的情况具有较好的性能。缺点需要构建和维护堆或二叉排序树增加了空间复杂度和实现的复杂性。对于一些简单的场景可能过于复杂。
二未来探索方向
进一步优化时间复杂度可以探索更高效的算法和数据结构以降低合并 k 个升序链表的时间复杂度。例如研究新的分治策略或者改进堆排序的实现以减少比较次数和操作次数。空间复杂度的优化在保证时间效率的同时尽量降低空间复杂度。可以考虑使用更紧凑的数据结构或者优化算法的内存使用以减少内存占用。结合实际应用场景进行优化根据不同的应用场景对算法进行针对性的优化。例如在数据库管理系统中可以考虑利用数据库的索引结构来加速链表的合并在图形处理中可以根据图形的特点和需求选择合适的合并策略。并行计算的应用对于大规模数据和链表数量较多的情况可以考虑使用并行计算技术将合并操作分配到多个处理器上同时进行以提高效率。动态调整算法根据输入数据的特点和规模动态地选择最合适的合并算法。例如当链表数量较少时可以使用简单的暴力方法当链表数量较多时自动切换到分治或堆排序方法。 总之合并 k 个升序链表是一个具有挑战性的问题通过不断地探索和创新可以找到更高效、更实用的解决方案为实际应用提供更好的支持。
