SHARE
TWEET

Untitled

bbescos Mar 3rd, 2019 70 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. class VectorSorter {
  83. public:
  84.     VectorSorter(const vector<vector<int>>& lists);
  85.     int Get();
  86. private:
  87.     vector<int> positions_;
  88.     vector<vector<int>> lists_;
  89.     vector<Element> elements_;
  90.     priority_queue<Element, vector<Element>, Compare> pq_;
  91. };
  92.  
  93. VectorSorter::VectorSorter(const vector<vector<int>>& lists) : positions_(lists.size(), 0), lists_(lists) {
  94.    
  95.     elements_.reserve(lists.size());
  96.     for (int i = 0; i < lists.size(); ++i) {
  97.         if (!lists[i].empty()) {
  98.             Element new_element(lists[i][0], i);
  99.             elements_.emplace_back(new_element);
  100.         }
  101.     }
  102.    
  103.     // O(k)
  104.     pq_ = priority_queue<Element, vector<Element>, Compare> (elements_.begin(), elements_.end());
  105. }
  106.  
  107. int VectorSorter::Get() {
  108.    
  109.     int solution;
  110.    
  111.     if (!pq_.empty()) {
  112.         Element current = pq_.top();
  113.         ++positions_[current.index];
  114.         solution = current.val;
  115.        
  116.         pq_.pop();
  117.        
  118.         if (positions_[current.index] < lists_[current.index].size()) {
  119.             Element next(lists_[current.index][positions_[current.index]], current.index);
  120.             pq_.push(next);
  121.         }
  122.     }
  123.     else
  124.         std::cout << "No more elements" << std::endl;
  125.    
  126.     return solution;
  127. }
  128.  
  129. int main()
  130. {
  131.     vector<vector<int>> lists{{1, 2, 4}, {3}, {1, 5}, {0}};
  132.  
  133.     VectorSorter vector_sorter(lists);
  134.  
  135.     int next_element = vector_sorter.Get();
  136.     std::cout << next_element << std::endl;
  137.     next_element = vector_sorter.Get();
  138.     std::cout << next_element << std::endl;
  139.     next_element = vector_sorter.Get();
  140.     std::cout << next_element << std::endl;
  141.     next_element = vector_sorter.Get();
  142.     std::cout << next_element << std::endl;
  143.     next_element = vector_sorter.Get();
  144.     std::cout << next_element << std::endl;
  145.     next_element = vector_sorter.Get();
  146.     std::cout << next_element << std::endl;
  147.     next_element = vector_sorter.Get();
  148.     std::cout << next_element << std::endl;
  149.     next_element = vector_sorter.Get();
  150.     std::cout << next_element << std::endl;
  151.  
  152.     return 0;
  153. }
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