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.

给定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]。

完整代码如下:

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

本代码提交AC,用时1016MS。

因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。

求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下:

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

本代码提交AC,用时56MS。

 

Leave a Reply

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