632. 最小區間

難度困難235收藏分享切換為英文關注反饋

四間小區、你有?k?個升序排列的整數列表。找到一個最小區間，使得?k?個列表中的每個列表至少有一個數包含在其中。

我們定義如果?b-a < d-c?或者在?b-a == d-c?時?a < c，則區間 [a,b] 比 [c,d] 小。

?

leetcode最大數？示例：

輸入：[[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] 中。

?

提示：

• 給定的列表可能包含重復元素，所以在這里升序表示 >= 。
• 1 <=?k?<= 3500
• -105?<=?元素的值?<= 105
• 對于使用Java的用戶，請注意傳入類型已修改為List<List<Integer>>。重置代碼模板后可以看到這項改動。

leetcode124，通過次數14,960提交次數25,456

這道題用二分，剪剪枝然后循環過一下就好了、

時間復雜度是O(k*n*log(k*n))

#include<stdio.h>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>::iterator getbinary(vector<int> &v,int n)
{int nleft = 0;int nright = v.size() - 1;int mid = (nleft + nright) / 2;while (nleft < nright){int Val = *(v.begin() + mid);if (Val >= n){nright = mid - 1;}else if (Val < n){nleft = mid + 1;}mid = (nleft + nright) / 2;}return v.begin() + nleft;
}
vector<int>::iterator getmaxmin(vector<int> &v, int n)
{if(*v.begin() == n)return v.begin();if (*v.begin() > n)return v.end();if (*(v.end() - 1) > n){vector<int>::iterator it = getbinary(v, n);if (*it > n)return it-1;else return it;}     return v.end()-1;
}
vector<int>::iterator getminmax(vector<int> &v, int n)
{if (*(v.end() - 1) < n)return v.end();if (*v.begin() >= n)return v.begin();vector<int>::iterator it = getbinary(v, n);if (*it >= n)return it;else return it + 1;}
vector<int> smallestRange(vector<vector<int>>& nums) {int nleft,nright = 0;int nLen = 200000;vector<int> nums_max;vector<int> v_ans;v_ans.clear();for (auto it = nums.begin(); it != nums.end(); it++){auto itit = it->begin();for (itit; itit != it->end(); itit++){nums_max.push_back(*itit);}}sort(nums_max.begin(), nums_max.end());int num = -100001;for (auto mit = nums_max.begin(); mit != nums_max.end(); mit++){nright = *mit;if (nright == num){continue;}else{num = nright;}int nflag = 0;int nmax = 100001;for (auto nit = nums.begin(); nit != nums.end(); nit++){vector<int>::iterator rit = getmaxmin(*nit, nright);if (rit != nit->end()){if (nmax > *rit)nmax = *rit;}if (rit == nit->end()){nflag = 1;break;}}if (nflag != 1){nleft = nmax;if (nright - nleft < nLen){v_ans.clear();v_ans.push_back(nleft);v_ans.push_back(nright);nLen = nright - nleft;}}nleft = *mit;nflag = 0;nmax = -100001;for (auto nit = nums.begin(); nit != nums.end(); nit++){vector<int>::iterator rit = getminmax(*nit, nright);if (rit != nit->end())if (nmax < *rit)nmax = *rit;if (rit == nit->end()){nflag = 1;break;}}if (nflag)continue;nright = nmax;if (nright - nleft < nLen){v_ans.clear();v_ans.push_back(nleft);v_ans.push_back(nright);nLen = nright - nleft;}}return v_ans;
}
int main()
{vector<vector<int>> nums;// = [[-89, 1, 69, 89, 90, 98], [-43, -36, -24, -14, 49, 61, 66, 69], [73, 94, 94, 96], [11, 13, 76, 79, 90], [-40, -20, 1, 9, 12, 12, 14], [-91, -31, 0, 21, 25, 26, 28, 29, 29, 30], [23, 88, 89], [31, 42, 42, 57], [-2, 6, 11, 12, 12, 13, 15], [-3, 25, 34, 36, 39], [-7, 3, 29, 29, 31, 32, 33], [4, 11, 14, 15, 15, 18, 19], [-34, 9, 12, 19, 19, 19, 19, 20], [-26, 4, 47, 53, 64, 64, 64, 64, 64, 65], [-51, -25, 36, 38, 50, 54], [17, 25, 38, 38, 38, 38, 40], [-30, 12, 15, 19, 19, 20, 22], [-14, -13, -10, 68, 69, 69, 72, 74, 75], [-39, 42, 70, 70, 70, 71, 72, 72, 73], [-67, -34, 6, 26, 28, 28, 28, 28, 29, 30, 31]];vector<int >v;/* v.push_back(4);v.push_back(10);v.push_back(15);v.push_back(24);v.push_back(26);nums.push_back(v);v.clear();v.push_back(0);v.push_back(9);v.push_back(12);v.push_back(20);nums.push_back(v);v.clear();v.push_back(5);v.push_back(18);v.push_back(22);v.push_back(30);nums.push_back(v);*//* v.push_back(-5);v.push_back(-4);v.push_back(-3);v.push_back(-2);v.push_back(-1);v.push_back(0);nums.push_back(v);v.clear();v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);nums.push_back(v);v.clear();v.push_back(5);v.push_back(18);v.push_back(22);v.push_back(30);nums.push_back(v);*//*v.push_back(10);v.push_back(10);nums.push_back(v);v.clear();v.push_back(11);v.push_back(11);nums.push_back(v);*//* int a[13] = { 11,14,8,11,8,21,15,20,15,24,19,17,12};for (int i = 0; i < 13; i++){int n;for (int j = 0; j < a[i]; j++){scanf("%d", &n);v.push_back(n);}   nums.push_back(v);v.clear();}*/v.push_back(1);v.push_back(2);v.push_back(3);nums.push_back(v);v.clear();v.push_back(1);v.push_back(2);v.push_back(3);nums.push_back(v);v.clear();v.push_back(1);v.push_back(2);v.push_back(3);nums.push_back(v);vector<int> v_ans = smallestRange(nums);auto it = v_ans.begin();for (it; it != v_ans.end(); it++){cout << *it << endl;}return 0;
}

?