[leetcode]632. Smallest Range

題目連結：https://leetcode.com/problems/smallest-range/description/

You have 

k

 lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the 

k

lists.

We define the range [a,b] is smaller than range [c,d] if 

b-a < d-c

 or 

a < c

 if 

b-a == d-c

.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
      

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= 

   k

    <= 3500
3. -105 <= 

   value of elements

    <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

這道題給了我們一些數組，都是排好序的，讓我們求一個最小的範圍，使得這個範圍内至少會包括每個數組中的一個數字。雖然每個數組都是有序的，但是考慮到他們之間的數字差距可能很大，是以我們最好還是合并成一個數組統一處理比較好，但是合并成一個大數組還需要保留其原屬數組的序号，是以我們大數組中存pair對，同時儲存數字和原數組的序号。然後我們重新按照數字大小進行排序，這樣我們的問題實際上就轉換成了求一個最小視窗，使其能夠同時包括所有數組中的至少一個數字。這不就變成了那道Minimum Window Substring。是以說啊，這些題目都是換湯不換藥的，總能變成我們見過的類型。我們用兩個指針left和right來确定滑動視窗的範圍，我們還要用一個哈希表來建立每個數組與其數組中數字出現的個數之間的映射，變量cnt表示目前視窗中的數字覆寫了幾個數組，diff為視窗的大小，我們讓right向右滑動，然後判斷如果right指向的數字所在數組沒有被覆寫到，cnt自增1，然後哈希表中對應的數組出現次數自增1，然後我們循環判斷如果cnt此時為k(數組的個數)且left不大于right，那麼我們用目前視窗的範圍來更新結果，然後此時我們想縮小視窗，通過将left向右移，移動之前需要減小哈希表中的映射值，因為我們去除了數字，如果此時映射值為0了，說明我們有個數組無法覆寫到了，cnt就要自減1。這樣周遊後我們就能得到最小的範圍了，參見代碼如下：

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> res;
        vector<pair<int,int>> v;
        unordered_map<int,int> m;
        for(int i=0;i<nums.size();i++)
        {
            for(int num:nums[i])
            {
                v.push_back({num,i});
            }
        }
        sort(v.begin(),v.end());
        int left=0,n=v.size(),k=nums.size(),cnt=0,diff=INT32_MAX;
        for(int right=0;right<n;++right)
        {
            if(m[v[right].second]==0) ++cnt;
            ++m[v[right].second];
            while(cnt==k && left<=right)
            {
                if(diff>v[right].first-v[left].first)
                {
                    diff=v[right].first-v[left].first;
                    res={v[left].first,v[right].first};
                }
                if(--m[v[left].second]==0) --cnt;
                ++left;
            }
        }
        return res;
    }
};