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

给定k个升序数组,求一个整数区间,该区间能至少包括所有数组的一个元素,且该区间最小。最小的定义是区间长度最小,如果区间长度相同,则区间起始点小则小。 参考Find smallest range containing elements from k lists这篇博客,突然发现GeeksforGeeks网站上的题比Leetcode上的多好多,而且都有详细题解和代码,好棒。 要求区间最小,则区间只包括每个数组的一个元素最好,所以我们要找k个数组中的k个数,使得这k个数的最大值和最小值的差最小,那么这个区间的两个端点就是这个最大值和最小值。 所以我们对k个数组维护k个指针,初始时都指向每个数组的首元素,然后找到这k个数的最大值和最小值,得到一个区间及其长度。然后我们不断循环:向前移动k个指针中的最小者,在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束,则返回得到的最小区间。 以样例为例。
  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]。
完整代码如下: [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。  ]]>

Leave a Reply

Your email address will not be published. Required fields are marked *