LeetCode Smallest Range

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 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.

1. i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
2. 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
3. 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
4. ++k，新数组[10,9,18]，区间[9,18]，长度为9。
5. ++j，新数组[10,12,18]，区间[10,18]，长度为8。
6. ++i，新数组[15,12,18]，区间[12,18]，长度为6。
7. ++j，新数组[15,20,18]，区间[15,20]，长度为5。
8. ++i，新数组[24,20,18]，区间[18,24]，长度为6。
9. ++k，新数组[24,20,22]，区间[20,24]，长度为4。
10. ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。

```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 };
}
};
```

```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 };
}
};
```