FB一面，还是热乎的

Mark一下merge sort.

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

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

snowwolf 发表于 2015-10-27 00:46
我的意思是如果要bruteforce就每次遍历头，O(L*K*K)
如果要好一点的就用heap来选择头，O(L*K*log K)
或 ...

恩，就是这样

第二题，用 divide and conquer 挺好的，复杂度跟heap一样，还比用heap要灵活多变。

1. vector<int> mergeKVector(vector<vector<int>> &lists) {
   
2.     vector<int> result;
   
3.     if(lists.empty()) return result;
   
4.     return helper(lists, 0, lists.size() - 1);
   
5. }
   
6. 
   
7. vector<int> helper(vector<vector<int>> &lists, int low, int high) {
   
8.     if(low >= high) return lists[low];
   
9.     int mid = low + (high - low) / 2;
   
10.     vector<int> left = helper(lists, low, mid);
    
11.     vector<int> right = helper(lists, mid + 1, high);
    
12.     return mergeTwoVector(left, right);
    
13. }
    
14. 
    
15. vector<int> mergeTwoVector(vector<int> a, vector<int> b) {
    
16.     vector<int> result(a.size() + b.size(), 0);
    
17.     int i = 0, j = 0;
    
18.     for(int k = 0; k < result.size(); ++k) {
    
19.         if(i < a.size() && j < b.size()) {
    
20.             if(a[i] < b[j]) result[k] = a[i++];
    
21.             else result[k] = b[j++];
    
22.         } else if(i < a.size()) {
    
23.             result[k] = a[i++];
    
24.         } else if(j < b.size()) {
    
25.             result[k] = b[j++];
    
26.         }
    
27.     }
    
28.     return result;
    
29. }
    
30. 
    
31. int  main() {
    
32.     vector<int> v1 = {3, 5, 6, 8, 22, 33, 44, 55};
    
33.     vector<int> v2 = {1, 4, 7, 9, 11, 13, 14 ,15, 18, 35, 61};
    
34.     vector<int> v3 = {1, 2, 10};
    
35.     vector<int> v4 = {20, 30, 40, 50, 60, 70, 80};
    
36. 
    
37.     vector<vector<int>> lists = {v1, v2, v3, v4};
    
38. 
    
39.     vector<int> result = mergeKVector(lists);
    
40. 
    
41.     for(auto l : lists) {
    
42.         for(int n : l) {
    
43.             cout << n << " ";
    
44.         }
    
45.         cout << endl;
    
46.     }
    
47.     for(int r : result) cout << r << " ";
    
48. 
    
49. 
    
50.     return 0;
    
51. }

复制代码

xuchen1m3fd 发表于 2015-10-26 12:47
bruteforce其实是两种，一种是全部扔进heap一种是遍历头找最小，两种复杂度不一样。但是heap不是O(KLlogK ...

就是heap里不是光存那个int，还存一下当前这个int是从哪个array里取的就好了，弄个pair，也没太复杂

akluffy 发表于 2015-11-1 00:41
第二题，用 divide and conquer 挺好的，复杂度跟heap一样，还比用heap要灵活多变。

恩，我用的就是这种方法，感觉更有的说道

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

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