Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- // k = number of lists
- // N = number of elements
- // n_k = number of element in list k
- // What happens if every list is not sorted?
- // O(NlogN) if I merge all vectors and I sort them
- // O(Nlogk) + O(N*log(N/k)) -> O(NlogN) if I sort all vectors and do heaps and I merge them
- // What happens if every list is sorted?
- // O(NlogN) if I merge all vectors and I sort them
- // O(Nlogk) if I take the min every time with heaps and I merge them
- // O(Nk) if I take the min every time without using heaps and I merge them <-
- struct Element {
- int val;
- int index;
- Element(int val, int index) : val(val), index(index) {};
- };
- struct Compare {
- bool operator() (const Element& e1, const Element& e2) {
- return(e1.val > e2.val);
- }
- };
- void PrintVector(const vector<Element>& nums) {
- for (Element num : nums)
- std::cout << num.val << " ";
- std::cout << std::endl;
- }
- // O(Nlogk)
- vector<int> MergeKVectors(const vector<vector<int>>& lists) {
- vector<Element> elements;
- elements.reserve(lists.size());
- for (int i = 0; i < lists.size(); ++i) {
- if (!lists[i].empty()) {
- Element new_element(lists[i][0], i);
- elements.emplace_back(new_element);
- }
- }
- // O(k)
- priority_queue<Element, vector<Element>, Compare> pq(elements.begin(), elements.end());
- vector<int> solution;
- vector<int> positions(lists.size(), 0);
- // O(Nlogk)
- while (!pq.empty()) {
- Element current = pq.top();
- solution.emplace_back(current.val);
- ++positions[current.index];
- // O(logk)
- pq.pop();
- if (positions[current.index] < lists[current.index].size()) {
- Element next(lists[current.index][positions[current.index]], current.index);
- // O(logk)
- pq.push(next);
- }
- }
- return solution;
- }
- void PrintVector(const vector<int>& nums) {
- for (int num : nums)
- std::cout << num << " ";
- std::cout << std::endl;
- }
- class VectorSorter {
- public:
- VectorSorter(const vector<vector<int>>& lists);
- int Get();
- private:
- vector<int> positions_;
- vector<vector<int>> lists_;
- vector<Element> elements_;
- priority_queue<Element, vector<Element>, Compare> pq_;
- };
- VectorSorter::VectorSorter(const vector<vector<int>>& lists) : positions_(lists.size(), 0), lists_(lists) {
- elements_.reserve(lists.size());
- for (int i = 0; i < lists.size(); ++i) {
- if (!lists[i].empty()) {
- Element new_element(lists[i][0], i);
- elements_.emplace_back(new_element);
- }
- }
- // O(k)
- pq_ = priority_queue<Element, vector<Element>, Compare> (elements_.begin(), elements_.end());
- }
- int VectorSorter::Get() {
- int solution;
- if (!pq_.empty()) {
- Element current = pq_.top();
- ++positions_[current.index];
- solution = current.val;
- pq_.pop();
- if (positions_[current.index] < lists_[current.index].size()) {
- Element next(lists_[current.index][positions_[current.index]], current.index);
- pq_.push(next);
- }
- }
- else
- std::cout << "No more elements" << std::endl;
- return solution;
- }
- int main()
- {
- vector<vector<int>> lists{{1, 2, 4}, {3}, {1, 5}, {0}};
- VectorSorter vector_sorter(lists);
- int next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- next_element = vector_sorter.Get();
- std::cout << next_element << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement