难度困难
你有 k
个 非递减排列 的整数列表。找到一个 最小 区间,使得 k
个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c
或者在 b-a == d-c
时 a < c
,则区间 [a,b]
比 [c,d]
小。
示例 1:
输入:nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出:[20,24] 解释: 列表 1:[4, 10, 15, 24, 26],24 在区间 [20,24] 中。 列表 2:[0, 9, 12, 20],20 在区间 [20,24] 中。 列表 3:[5, 18, 22, 30],22 在区间 [20,24] 中。
示例 2:
输入:nums = [[1,2,3],[1,2,3],[1,2,3]] 输出:[1,1]
class Solution { public: vector<int> smallestRange(vector<vector<int>>& nums) { vector<pair<int,int>> n_list; for(int i = 0; i < nums.size();i++) { for(auto num: nums[i]) { n_list.push_back({num,i}); } } sort(n_list.begin(),n_list.end()); //sort(n_list.begin(),n_list.end(),[](auto a, auto b){ // return a.first < b.first; //}); vector<int> res = {0,INT_MAX}; int l = 0, r = 0; int len = INT_MAX; unordered_map<int,int> cnt_map; while(r < n_list.size()) { int index = n_list[r].second; cnt_map[index]++; r++; while (cnt_map.size() == nums.size()) { int cur_len = n_list[r-1].first - n_list[l].first; if ( cur_len < len) { res[0] = n_list[l].first; res[1] = n_list[r-1].first; len = cur_len; } int l_index = n_list[l].second; cnt_map[l_index]--; if (cnt_map[l_index] == 0) { cnt_map.erase(l_index); } l++; } } return res; } };
标签:24,map,632,20,int,list,最小,cnt,区间 From: https://www.cnblogs.com/zle1992/p/16610523.html