第一题：逆波兰表达式
来源https://blog.csdn.net/qq_36237037/article/details/106629009
第二题.题目描述
来源https://blog.csdn.net/qq_36237037/article/details/106644664
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
一 思路一 最笨方法
将所有节点添加到一个数组中
对数组中的节点从小到大进行排序
从数组中从小到大依次取出节点，串成链表
二 思路二 逐一比较
第一步：找到所有链表中的最小的一个结点
把这个结点赋值给创建的链表的head，然后再把最小的链表的下一个结点赋值给这个链表，然后有一个while循环，直到所有链表 不满足条件，不赋值为止，跳出循环。
/// 方法二 逐一比较
- (LinkNode *)mergeManyLists2:(NSMutableArray<LinkNode *> *)linkNodes {
if (linkNodes == nil || linkNodes.count == 0) {
return nil;
}
LinkNode *head = [[LinkNode alloc] init];
LinkNode *cur = head;
while (true) {
int minIndex = -1;
for (int i = 0; i < linkNodes.count; i++) {
if (linkNodes[i] == nil || linkNodes[i].element == nil) {
continue;
}
if (minIndex == -1 || linkNodes[i].value < linkNodes[minIndex].value) {
minIndex = i;
}
}
if (minIndex == -1) {
break;
}
cur = cur.next = linkNodes[minIndex];
linkNodes[minIndex] = linkNodes[minIndex].next;
}
return head.next;
}
方法三递归有点问题应该使用
因为递归的时间复杂度是2的n次方，上面的方式是kn
第一种时间复杂度是O(nlogn)
空间复杂度是：O（n）
第二种时间复杂度是O(kn)
第三种时间复杂度是：O(kn)
第四种时间复杂度是：O(nLogk)
空间复杂度是O(k)
第五种时间复杂度是O(nlogk)
网友评论