SHARE
TWEET

Untitled

bbescos Mar 3rd, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. // k = number of lists
  7. // N = number of elements
  8. // n_k = number of element in list k
  9.  
  10. // What happens if every list is not sorted?
  11. // O(NlogN) if I merge all vectors and I sort them
  12. // O(Nlogk) + O(N*log(N/k)) -> O(NlogN) if I sort all vectors and do heaps and I merge them
  13.  
  14. // What happens if every list is sorted?
  15. // O(NlogN) if I merge all vectors and I sort them
  16. // O(Nlogk) if I take the min every time with heaps and I merge them
  17. // O(Nk) if I take the min every time without using heaps and I merge them <-
  18.  
  19. struct Element {
  20.     int val;
  21.     int index;
  22.     Element(int val, int index) : val(val), index(index) {};
  23. };
  24.  
  25. struct Compare {
  26.     bool operator() (const Element& e1, const Element& e2) {
  27.         return(e1.val > e2.val);
  28.     }
  29. };
  30.  
  31. void PrintVector(const vector<Element>& nums) {
  32.     for (Element num : nums)
  33.         std::cout << num.val << " ";
  34.  
  35.     std::cout << std::endl;
  36. }
  37.  
  38. // O(Nlogk)
  39. vector<int> MergeKVectors(const vector<vector<int>>& lists) {
  40.    
  41.     vector<Element> elements;
  42.     elements.reserve(lists.size());
  43.     for (int i = 0; i < lists.size(); ++i) {
  44.         if (!lists[i].empty()) {
  45.             Element new_element(lists[i][0], i);
  46.             elements.emplace_back(new_element);
  47.         }
  48.     }
  49.    
  50.     // O(k)
  51.     priority_queue<Element, vector<Element>, Compare> pq(elements.begin(), elements.end());
  52.    
  53.     vector<int> solution;
  54.     vector<int> positions(lists.size(), 0);
  55.    
  56.     // O(Nlogk)
  57.     while (!pq.empty()) {
  58.         Element current = pq.top();
  59.         solution.emplace_back(current.val);
  60.         ++positions[current.index];
  61.        
  62.         // O(logk)
  63.         pq.pop();
  64.        
  65.         if (positions[current.index] < lists[current.index].size()) {
  66.             Element next(lists[current.index][positions[current.index]], current.index);
  67.             // O(logk)
  68.             pq.push(next);
  69.         }
  70.     }
  71.    
  72.     return solution;
  73. }
  74.  
  75. void PrintVector(const vector<int>& nums) {
  76.     for (int num : nums)
  77.         std::cout << num << " ";
  78.  
  79.     std::cout << std::endl;
  80. }
  81.  
  82. int main()
  83. {
  84.     vector<vector<int>> lists{{1, 2, 4}, {3}, {1, 5}, {0}};
  85.  
  86.     vector<int> sorted_list = MergeKVectors(lists);
  87.  
  88.     PrintVector(sorted_list);
  89.  
  90.     return 0;
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top