c++ priority_queue solution with detailed explanation


  • 0
    Q

    We use the priority_queue to solve this problem. The format of element in priority_queue is pair(pair<int,int> First element represents the value and 2nd element represents the list number). Also we use an array cur[] to preserve the current index of each list. Once we reached the end point of one list, we yield the result.
    With priority_queue, we can easily get the smallest element in log(n) time and we get the difference between smallest element and largest element. Then we advance that list until we get to the end point of one particular list.

    class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            //bfs
            struct compare{
              bool operator()(pair<int,int> a, pair<int,int> b){
                  return a.first > b.first;
              }  
            };
            vector<int> res(2,0);
            vector<int> cur(nums.size(),0);
            if(nums.size() == 0 || nums[0].size() == 0)
                return res;
            priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq;
            int max=INT_MIN;
            
            for(int i=0;i<nums.size();i++){
                pq.push({nums[i][0],i});
                if(nums[i][0]>max)
                    max = nums[i][0];
            }
            
            int diff = INT_MAX;
            while(1){
                pair<int, int> t = pq.top();
                pq.pop();
                //cout<<"line 27 "<<t.first<<" "<<t.second<<endl;
                int n_diff = max - t.first;
                if(n_diff < diff){
                    res[0] = t.first;
                    res[1] = max;
                    diff = n_diff;
                }
                cur[t.second]++;
                if(cur[t.second] == nums[t.second].size())
                    break;
                else{
                    pq.push({nums[t.second][cur[t.second]], t.second});
                    if(nums[t.second][cur[t.second]] > max)
                        max = nums[t.second][cur[t.second]];
                }
                
            }
            return res;
        }
    };
    

Log in to reply
 

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