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,d] 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.
题意：
给定一些sorted array, 求一个最小范围，使得该范围内至少包含每个数组中的一个数字。
思路：
这个题来自打车公司lyft，现实意义是模拟该app在很多user登陆的登陆时间，narrow一个范围，这样就可以在user登陆时间最频繁的范围里投放广告或者做些其他的商业行为。
two pointer的思路。
三个指针zero、first、second同时从每个list的首元素出发。用pointerIndex来维护一个数组记录每个list当前指针的index。
比较三个指针对应的元素大小。记录比较后的curMin, curMax，更新smallest range。
移动curMin对应的指针，比较三个指针对应的元素大小。记录比较后的curMin, curMax，更新smallest range。 更新pointerIndex。
直至curMin对应的指针无法移动为止（即curMin走到了某个list的尽头）。
[4,10,15,24,26] ^ zero [0,9,12,20] ^ first [5,18,22,30] ^ second
curMin curMax range pointerIndex
zero|first|second
init 0 5 5 0 | 0 | 0
curMin对应的指针first++ 4 9 5 0 | 1 | 0
curMin对应的指针zero++ 5 10 5 1 | 1 | 0
curMin对应的指针second++ 9 18 9 1 | 1 | 1
curMin对应的指针first++ 10 18 8 1 | 2 | 1
curMin对应的指针zero++ 12 18 6 2 | 2 | 1
curMin对应的指针first++ 15 20 5 2 | 3 | 1
curMin对应的指针zero++ 18 24 6 3 | 3 | 1
curMin对应的指针second++ 20 24 4 3 | 3 | 2
代码一：
1 public int[] smallestRange2(List<List<Integer>> nums) { 2 int curMin = 0; 3 int curMax = Integer.MAX_VALUE; 4 int[] pointerIndex = new int[nums.size()];// maintain一个数组来记录每层list当前的pointer的index 5 boolean flag = true; // flag辅助判断是否有某个list走到了末尾 6 7 for (int i = 0; i < nums.size() && flag; i++) { // 外层循环遍历list 8 for (int j = 0; j < nums.get(i).size() && flag; j++) { // 内层循环遍历某个list的第 j 个元素 9 int minValueLevel = 0; 10 int maxValueLevel = 0; 11 for (int k = 0; k < nums.size(); k++) { 12 if (nums.get(minValueLevel).get(pointerIndex[minValueLevel]) > nums.get(k).get(pointerIndex[k])) { 13 minValueLevel = k; 14 } 15 if (nums.get(maxValueLevel).get(pointerIndex[maxValueLevel]) < nums.get(k).get(pointerIndex[k])) { 16 maxValueLevel = k; 17 } 18 } 19 // 是否更新smallest range 20 if (nums.get(maxValueLevel).get(pointerIndex[maxValueLevel]) - nums.get(minValueLevel).get(pointerIndex[minValueLevel]) < curMax - curMin) { 21 curMin = nums.get(minValueLevel).get(pointerIndex[minValueLevel]); 22 curMax = nums.get(maxValueLevel).get(pointerIndex[maxValueLevel]); 23 } 24 // 移动当前找到的最小值对应的pointer 25 pointerIndex[minValueLevel]++; 26 // flag辅助判断是否有某个list走到了末尾 27 if (pointerIndex[minValueLevel] == nums.get(minValueLevel).size()) { 28 flag = false; 29 break; 30 } 31 32 } 33 } 34 return new int[]{curMin, curMax}; 35 }这个代码在oj上显示time limit exceeded
因为每次都要比较三个指针对应元素的curMin和curMax, 我们可以用一个PriorityQueue来优化。
PriorityQueue里面存放当前三个指针对应的元素。
PriorityQueue 删除极值的时间复杂度是 O(logN), 查找极值的时间复杂度是 O(1)
能够在时间上进行优化。
代码二：
1 public int[] smallestRange(List<List<Integer>> nums) { 2 int curMin = 0; 3 int curMax = Integer.MAX_VALUE; 4 int max = Integer.MIN_VALUE; 5 int[] pointerIndex = new int[nums.size()]; 6 boolean flag = true; 7 PriorityQueue<Integer> queue = new PriorityQueue<Integer>((i, j) -> nums.get(i).get(pointerIndex[i]) - nums.get(j).get(pointerIndex[j])); 8 for (int i = 0; i < nums.size(); i++) { 9 queue.add(i); 10 max = Math.max(max, nums.get(i).get(0)); 11 } 12 for (int i = 0; i < nums.size() && flag; i++) { 13 for (int j = 0; j < nums.get(i).size() && flag; j++) { 14 int minValueLevel = queue.poll(); 15 // 是否更新smallest range 16 if (max - nums.get(minValueLevel).get(pointerIndex[minValueLevel]) < curMax - curMin) { 17 curMin = nums.get(minValueLevel).get(pointerIndex[minValueLevel]); 18 curMax = max; 19 } 20 // 移动当前找到的最小值对应的pointer 21 pointerIndex[minValueLevel]++; 22 // flag辅助判断是否有某个list走到了末尾 23 if (pointerIndex[minValueLevel] == nums.get(minValueLevel).size()) { 24 flag = false; 25 break; 26 } 27 queue.offer(minValueLevel); 28 max = Math.max(max, nums.get(minValueLevel).get(pointerIndex[minValueLevel])); 29 30 } 31 } 32 return new int[]{curMin, curMax}; 33 }
转载于:https://www.cnblogs.com/liuliu5151/p/9075031.html
