Clean C++ priority_queue solution using iterators


  • 15
    A

    Yes. The idea is just similar to Merge K Sorted List. Keep a priority queue of iterators/pointers which points to the current head of a row.

    class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            typedef vector<int>::iterator vi;
            
            struct comp {
                bool operator()(pair<vi, vi> p1, pair<vi, vi> p2) {
                    return *p1.first > *p2.first;
                }
            };
            
            int lo = INT_MAX, hi = INT_MIN;
            priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, comp> pq;
            for (auto &row : nums) {
                lo = min(lo, row[0]);
                hi = max(hi, row[0]);
                pq.push({row.begin(), row.end()});
            }
            
            vector<int> ans = {lo, hi};
            while (true) {
                auto p = pq.top();
                pq.pop();
                ++p.first;
                if (p.first == p.second)
                    break;
                pq.push(p);
                
                lo = *pq.top().first;
                hi = max(hi, *p.first);
                if (hi - lo < ans[1] - ans[0])
                    ans = {lo, hi};
            }
            return ans;
        }
    };
    

  • 1

    @Aeonaxx
    The method of using iterators is cool!


  • 0
    A
    This post is deleted!

  • 0
    S

    a clean method

    class Solution {
    public:
    	struct Node
    	{
    		int val;
    		int i;
    		int j;
    
    		Node(int _val, int _i, int _j) :val(_val), i(_i), j(_j) {}
    	};
    	struct cmp
    	{
    		bool operator()(Node n1, Node n2)
    		{
    			return n1.val > n2.val;
    		}
    	};
    public:
    	vector<int> smallestRange(vector<vector<int>>& nums) {
    		priority_queue<Node,vector<Node>,cmp> my_pq;
    		int cur_min = INT_MAX, cur_max = INT_MIN,cur_range = INT_MAX;
    		int start, end;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			Node tem_node(nums[i][0], i, 0);
    			my_pq.push(tem_node);
    			cur_max = max(cur_max, nums[i][0]);
    		}
    
    		while (true)
    		{
    			auto top = my_pq.top();
    			my_pq.pop();
    			cur_min = top.val;
    			if (cur_max - cur_min < cur_range)
    			{
    				start = cur_min;
    				end = cur_max;
    				cur_range = end - start;
    			}
    
    			if ((top.j + 1) == nums[top.i].size())
    				break;
                Node next(nums[top.i][top.j + 1], top.i, top.j + 1);
    			my_pq.push(next);
    			if (next.val > cur_max)
    				cur_max = next.val;
    
    		}
    		vector<int> ret = { start,end };
    
    		return ret;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.