脸熟店面

听口音应该是华人小哥，上来闲聊自我介绍。
1. 以舅舅，秒过
2. 而散
不许使用heap/priorit

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

还是给了positive feedback，感谢这位小哥。。

儿散是要求merge 排序？

而散，如果不用 Priority Queue的話，我只想得到下面的解法，但使用 recursive的話會在stack上一直產生recursive call，這樣子的話還算O(1) 空間嗎?

1. public ListNode mergeKLists(ListNode[] lists) {
   
2.         if(lists.length == 0)
   
3.             return null;
   
4.         return divideAndConquer(0, lists.length-1, lists);
   
5.     }
   
6.    
   
7.     ListNode divideAndConquer(int start, int end, ListNode[] lists){
   
8.         if(start == end)
   
9.             return lists[start];
   
10.         int mid = start + ((end - start) >> 1);
    
11.         ListNode l1 = divideAndConquer(start, mid, lists);
    
12.         ListNode l2 = divideAndConquer(mid + 1, end, lists);
    
13.         return mergeTwoLists(l1,l2);
    
14.         
    
15.     }
    
16.    
    
17.     private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
18.         if(l1 == null)
    
19.             return l2;
    
20.         if(l2 == null)
    
21.             return l1;
    
22.         if(l1.val < l2.val)
    
23.             l1.next = mergeTwoLists(l1.next, l2);
    
24.         else
    
25.             l2.next = mergeTwoLists(l1, l2.next);
    
26.         return l1.val < l2.val ? l1 : l2;
    
27.     }

复制代码

楼主第二题怎么做的啊 有什么思路吗

lf963 发表于 2018-6-27 20:21
而散，如果不用 Priority Queue的話，我只想得到下面的解法，但使用 recursive的話會在stack上一直產生recu ...

Recursive换成Interative就避免调用栈了呀

补充内容 (2018-6-28 02:53):
* Iterative

mint0715 发表于 2018-6-27 10:52
Recursive换成Interative就避免调用栈了呀

补充内容 (2018-6-28 02:53):

Iterative的只用指针，不用一个 k (还是logk)大小的stack吗？总得记得自己在哪里，记得哪些是merge过的，merge完放到哪里吧………………

补充内容 (2018-7-3 12:40):
PS 我也只懂得那种recursive的写法 iterative的我用Queue但也是需要k space的