1、汇总概要
以下思路涵盖了归并、哈希、Comparator(Java自定义排序）等知识点
2、题目
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.
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.
【原题地址参见: [LeetCode]632. Smallest Range】
难度：Hard
3、审题
给定K组升序排列的整数数组，求最小范围，满足K组中每组至少有一个落在该范围内。
4、解题思路
为方便计，以题目中的example为例来讲解思路。
Step1：因求取的最小范围([20,24])的起始和结束位置K组list中的2个值（起始范围20属于list2，结束位置24属于list1）,为简单计 => 将几组list合并成一个大list，重新全排，得到：
[0,4,5,9,10,12,15,18,20,22,24,26,30
]
Step2：在大list中选取一最小的滑动窗口，使每组中至少有一个落于该窗口即可。
=> 需遍历大list求取窗口的起始和结束位置，
在每次遍历时，判断窗口范围内的值是否在K组list中都出现过（比如[20,24]在大list中表现的窗口为[20,22,24]，其中20属于list2, 22属于list3, 24属于list1）
以上Step1、Step2是较基本的解题思路，但是step2中下划线部分时间复杂度较高，需优化。
step3：为大list数组添加附加信息，如下(
l1,
l2,
l3分别表示该数据的来源数组）- 用hash表实现。
其中框框表示满足条件的滑动窗口(该窗口中同时包含l1,l2,l3),范围最小的窗口即是目标窗口
参考下图（图中的矩形框都满足条件，但是红色框是最优的一个）
5、代码示例 (JAVA)
class dataRange{
String source;
int flag;
}
public class SmallestRange {
public static void main(String [] args){
int []l1 = {4,10,15,24,26};
int []l2 = {0,9,12,20};
int []l3 = {5,18,22,30};
int len1 = l1.length;
int len2 = l2.length;
int len3 = l3.length;
int i=0,len;
len = len1+len2+len3;
System.out.println("len:"+len1+" "+len2+" "+len3);
dataObj arrd[] = new dataObj[len];
for(i=0;i<len1;i++){
arrd[i] = new dataObj(l1[i],"l1");
}
for(i=0;i<len2;i++){
arrd[len1+i] = new dataObj(l2[i],"l2");
}
for(i=0;i<len3;i++){
arrd[len1+len2+i] = new dataObj(l3[i],"l3");
}
//sort the array with flag of source
Arrays.sort(arrd, new ComparatorT());
System.out.println("\nafter sort-----");
for(i=0;i<len;i++){
System.out.println(arrd[i].value+" - "+arrd[i].source);
}
/*find the smallest range
* if the range includes "l1","l2","l3", then met the requirement, and find the smallest one
*/
int inNum = 0; //initial the num of includes "l1","l2","l3", if reach 3, put into optional result
int rangeStart = arrd[0].value;
int rangeEnd = arrd[len-1].value;
int range = rangeEnd - rangeStart;
int rangeStartCur = 0,rangeEndCur=0; //use in loop to find
HashMap <String,Integer>hmCur = new HashMap<String,Integer>();
i = 0;
int iStart = 0;
while(i<len){
if(inNum == 0){
iStart = i;
System.out.println("iStart ---"+iStart);
}
if(!hmCur.containsKey(arrd[i].source)){
hmCur.put(arrd[i].source,arrd[i].value);
inNum ++;
System.out.println(arrd[i].source+" inNum: "+inNum);
}
if(inNum == 1){
rangeStartCur = arrd[i].value;
}else if(inNum==3){
rangeEndCur = arrd[i].value;
if(rangeEndCur - rangeStartCur <= range){
rangeStart = rangeStartCur;
rangeEnd = rangeEndCur;
range = rangeEndCur - rangeStartCur;
}
//clear the hash
hmCur.clear();
inNum = 0;
i= iStart;
}
i ++;
System.out.println("i ---"+i);
}
System.out.println("\n result: ");
System.out.println("["+rangeStart+","+rangeEnd+"]");
}
}
其中排序调用到的class如下：
import java.util.*;
public class ComparatorT implements Comparator{
@Override
public int compare(Object o1,Object o2){
int k1 = ((dataObj)o1).value;
int k2 = ((dataObj)o2).value;
if (k1 > k2){
return 1; //大于时返回1，小于时返回-1，表示正序；反过来是反序
}
else{
return -1;
}
}
}
---------------------------------------------------------------------------------------------------
本文链接：http://blog.csdn.net/karen0310/article/details/75007486
请尊重作者的劳动成果，转载请注明出处！
---------------------------------------------------------------------------------------------------
