第一題：逆波蘭表達(dá)式
來(lái)源https://blog.csdn.net/qq_36237037/article/details/106629009
第二題.題目描述
來(lái)源https://blog.csdn.net/qq_36237037/article/details/106644664
合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。
一 思路一 最笨方法
將所有節(jié)點(diǎn)添加到一個(gè)數(shù)組中?
對(duì)數(shù)組中的節(jié)點(diǎn)從小到大進(jìn)行排序
從數(shù)組中從小到大依次取出節(jié)點(diǎn)，串成鏈表
二 思路二 逐一比較
第一步：找到所有鏈表中的最小的一個(gè)結(jié)點(diǎn)
把這個(gè)結(jié)點(diǎn)賦值給創(chuàng)建的鏈表的head，然后再把最小的鏈表的下一個(gè)結(jié)點(diǎn)賦值給這個(gè)鏈表，然后有一個(gè)while循環(huán)，直到所有鏈表 不滿足條件，不賦值為止，跳出循環(huán)。
/// 方法二 逐一比較
- (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;
}
方法三遞歸有點(diǎn)問(wèn)題應(yīng)該使用
因?yàn)檫f歸的時(shí)間復(fù)雜度是2的n次方，上面的方式是kn
第一種時(shí)間復(fù)雜度是O(nlogn)
空間復(fù)雜度是：O（n）
第二種時(shí)間復(fù)雜度是O(kn)
第三種時(shí)間復(fù)雜度是：O(kn)
第四種時(shí)間復(fù)雜度是：O(nLogk)
空間復(fù)雜度是O(k)
第五種時(shí)間復(fù)雜度是O(nlogk)
