LeetCode Smallest Range
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 language=",d"][/c] 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:
- The given list may contain duplicates, so ascending order means >= here.
- 1 <=
k <= 3500
- -105 <=
value of elements <= 105.
- 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.
给定k个升序数组，求一个整数区间，该区间能至少包括所有数组的一个元素，且该区间最小。最小的定义是区间长度最小，如果区间长度相同，则区间起始点小则小。
参考
Find smallest range containing elements from k lists这篇博客，突然发现GeeksforGeeks网站上的题比Leetcode上的多好多，而且都有详细题解和代码，好棒。
要求区间最小，则区间只包括每个数组的一个元素最好，所以我们要找k个数组中的k个数，使得这k个数的最大值和最小值的差最小，那么这个区间的两个端点就是这个最大值和最小值。
所以我们对k个数组维护k个指针，初始时都指向每个数组的首元素，然后找到这k个数的最大值和最小值，得到一个区间及其长度。然后我们不断循环：向前移动k个指针中的最小者，在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束，则返回得到的最小区间。
以样例为例。
- i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
- 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
- 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
- ++k，新数组[10,9,18]，区间[9,18]，长度为9。
- ++j，新数组[10,12,18]，区间[10,18]，长度为8。
- ++i，新数组[15,12,18]，区间[12,18]，长度为6。
- ++j，新数组[15,20,18]，区间[15,20]，长度为5。
- ++i，新数组[24,20,18]，区间[18,24]，长度为6。
- ++k，新数组[24,20,22]，区间[20,24]，长度为4。
- ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。
完整代码如下：
[cpp]
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();
vector<int> ptr(k, 0);
while (true) {
bool done = false;
int curmin = INT_MAX, curmax = INT_MIN, minid = 0;
for (int i = 0; i < k; ++i) {
if (ptr[i] >= nums[i].size()) {
done = true;
break;
}
if (nums[i][ptr[i]] < curmin) {
curmin = nums[i][ptr[i]];
minid = i;
}
if (nums[i][ptr[i]] > curmax) {
curmax = nums[i][ptr[i]];
}
}
if (done)break;
if (curmax – curmin < ansrange) {
ansrange = curmax – curmin;
ansmin = curmin;
ansmax = curmax;
}
++ptr[minid];
}
return{ ansmin,ansmax };
}
};
[/cpp]
本代码提交AC，用时1016MS。
因为每一轮都需要从k个数组中找最大值和最小值，线性查找的复杂度为O(k)。最坏情况下，需要遍历k个数组的每个元素，假设k个数组所有元素个数为n，则总的时间复杂度为O(nk)。
求k个数组的最大值和最小值的过程，可以用大小为k的优先队列（最小堆）来优化，复杂度可以降为O(nlgk)。代码如下：
[cpp]
class Solution {
private:
struct Node {
int value;
int idx;
int nxt;
Node(int v, int i, int n) :value(v), idx(i), nxt(n) {};
bool operator<(const Node& nd) const {
return value > nd.value;
}
bool operator>(const Node& nd) const {
return value < nd.value;
}
};
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size();
priority_queue<Node> pq;
for (int i = 0; i < k; ++i) {
pq.push(Node(nums[i][0], i, 1));
if (nums[i][0] < ansmin) {
ansmin = nums[i][0];
}
ansmax = max(ansmax, nums[i][0]);
}
int curmax = ansmax;
while (true) {
int curmin = pq.top().value;
int minidx = pq.top().idx;
int minnxt = pq.top().nxt;
pq.pop();
if (curmax – curmin < ansrange) {
ansrange = curmax – curmin;
ansmin = curmin;
ansmax = curmax;
}
if (minnxt < nums[minidx].size()) {
curmax = max(curmax, nums[minidx][minnxt]);
pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1));
}
else break;
}
return{ ansmin,ansmax };
}
};
[/cpp]
本代码提交AC，用时56MS。
]]>
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example: