求k个数组包含每个数组至少一个元素的最小范围（待字闺中，备忘）

例如：

 

1: 4, 10, 15, 24, 26

2: 0, 9, 12, 20

3: 5, 18, 22, 30

 

所得最小范围为[20,24]，其中，20在2中，22在3中，24在1中。

 

这是待字闺中的一道面试题，就个人经验来看一般有序数组的题目都会让人联想到有折半查找来解决，到有序数组为多个时，一般会联想到归并排序的思想，那么这道题就不例外。

 

以下引自待字闺中的分析：

那这个题目选择哪个方法继续尝试呢？那我们再分析一下要解决的问题。找到一个最小的范围，每一个有序数组中，都至少有一个元素在这个范围中。找到这样一个范围并不难，可是如何确定最小的范围呢？最终得到的最小的范围，至少包含三个元素，并且在所有数组整体的排序中，是相邻的。假设最小范围是[a, b, c]，a < b < c。 c-a是最小的。并且，a，b，c来自不同的有序数组。还有一种情况是[a,b,d,c]，a,b,c不是紧邻的，中间有一个d即： a< d < c。这时，d只能是来自b所在的数组，如下分析：

 

d来自a所在的数组，那么应有更短的范围c - d

 

d来自c所在的数组，那么应有更短的范围d - a

 

d来自b所在的数组，范围大小是不变的，就是无论是考虑d，还是考虑b。都没有影响。

 

从上面的分析，我们得出，只需要考虑在最终的排序中，考虑邻近的、并且来自不同有序数组的元素，作为备选的范围。那么该怎么样做到只考虑临近的、并且来自不同的有序数组的元素呢？这里就用到了归并排序的思想。以原题中的例子为例，假设有三个指针指，p1,p2,p3，分别指向三个数组的第一个元素：

 

步骤 指针当前值 最大值 最小值 min_range_value 移动指针

1 4,0,5 5 0 5 p2

2 4,9,5 9 4 5 p1

3 10,9,5 10 5 5 p3

4 10,9,18 18 9 9 p2

5 10,12,18 18 10 8 p1

6 15,12,18 18 12 6 p2

7 15,20,18 20 15 5 p1

8 24,20,18 24 18 6 p3

9 24,20,22 24 20 4 p2

end

结束是因为第二个数组已经没有元素可以再进行遍历了。最终得到最小的min_range_value为4，即为题目例子的答案。

 

上面这个方法，通过归并排序的思想，确保每次都是k个来自不同的数组的元素进行比较，得到最大值、最小值。就可以得到一个范围，包含了所有数组中的数字。

 

这个题的著名变种是从网页中产生包含所有查询词的最小的摘要。如果你 面过Google，你应该听说过这题。

 

个人的理解：

其实就是利用归并的思想，三个数组或更多个数组做归并排序，排在最小的元素向前移动，计算最大最小元素之间的间隔，这样当一个数组用尽的时候，记录的最小间隔即为所求。

 

/************************************************************************* 
        > File Name: mindiff.c 
        > Author: desionwang 
        > Mail: wdxin1322@qq.com  
        > Created Time: Wed 23 Oct 2013 02:57:44 PM CST 
 ************************************************************************/  
  
  
#include<stdio.h>  
  
  
int mindiff(int a[], int size_a, int b[], int size_b, int c[], int size_c){  
        int i = 0, j = 0 ,k = 0;  
        int minnum;  
        int mindiff = 65535;  
        if(a == NULL || b == NULL || c == NULL){  
                return -1;  
        }  
        if(size_a <= 0 || size_b <= 0 || size_c <= 0){  
                return -1;  
        }  
        int max, min, diff;  
        int index;  
        while(i < size_a && j < size_b && k < size_c){  
                printf("a:%d\tb:%d\tc:%d\n", a[i], b[j], c[k]);  
                if(a[i] >= b[j]){  
                        if(a[i] >= c[k]){  
                                max = a[i];  
                        }else{  
                                max = c[k];  
                        }  
                        if(b[j] <= c[k]){  
                                min = b[j];  
                                index = j;  
                                j++;  
                        }else{  
                                min = c[k];  
                                index = k;  
                                k++;  
                        }  
                }else{  
                        if(b[j] >= c[k]){  
                                max = b[j];  
                        }else{  
                                max = c[k];  
                        }  
                        if(a[i] <= c[k]){  
                                min = a[i];  
                                index = k;  
                                i++;  
                        }else{  
                                min = c[k];  
                                index = i;  
                                k++;  
                        }  
                }  
  
  
                printf("max:%d\tmin:%d\n", max, min);  
                //printf("a:%d\tb:%d\tc:%d\n", a[i], b[j], c[k]);  
                diff = max - min;  
                if(diff < mindiff){  
                        mindiff = diff;  
                }  
        }  
        //printf("a:%d\tb:%d\tc:%d\n", a[i], b[j--], c[k]);  
        printf("mindiff:%d\n", mindiff);  
        return mindiff;  
  
  
}  
  
  
int main(){  
        int a[5] = {4, 10, 15, 24, 26};  
        int b[] = {0, 9, 12, 20};  
        int c[] = {5, 18, 22, 30};  
        mindiff(a, 5, b, 4, c , 4);  
}  

 

 

补充：软件开发 , C++ ,