转：最小区间：k个有序的数组，找到最小区间使k个数组中每个数组至少有一个数在区间中

转：http://www.itmian4.com/thread-6504-1-1.html

最小区间原题

k个有序的数组，找到最小的区间范围使得这k个数组中，每个数组至少有一个数字在这个区间范围内。比如：

数组1：[4, 10, 15, 24, 26]

数组2：[0, 9, 12, 20]

数组3：[5, 18, 22, 30]

最小的区间是[20, 24]，这个区间包含了数组1中的24，数组2中的20，数组3中的22

思考时间~~~

分析

该题看起来还算比较简单，大家通常都会想到：为每一个数组设置一个遍历变量，选择最小值的数组，继续往后移动一位。由于是有k个数组，数组的数量有可能很多，所以如何去选择和替换最小的值，我们就会想到一个数据结构最小堆来维护最小的值。

解答方法：
初始化大小为k的最小堆，k个数字是每个数组中的最小值，设置变量maxValue记录k个数字中最大值，删除堆顶元素，将原堆顶元素对应的数组中下一个值加入到堆中，调整堆，并且记录当前区间范围（maxValue - minValue），重复执行直到某个数组所有值都被删除。

比如.
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

最小堆大小为3. 从三个数组中取最小值
Heap [0, 4, 5] maxValue 5
Range - 6

删除0 ，加入9
Heap [4, 9, 5] maxValue 9
Range - 6

删除4 ，加入10
Heap [5, 9, 10] maxValue 10
Range - 6

重复执行，最终得到结果

代码如下：
 struct pn

 {

     int n; /* belong to which array */

     int d; /* the data value */

     pn(int _n, int _d) { n = _n; d = _d; }

     pn(const pn& _pn) { n = _pn.n; d = _pn.d; }

 };

 inline void swap(pn& a, pn& b) { pn c = a; a = b; b = c; }

 void adjust(int n, pn a[])

 {

     int i = , max = ;

     int l = , r = ;

     for(i = n / ; i >= ; i--)

     {

         max = i;

         l =  * i + ;

         r =  * i + ;

         if(l < n && a[l].d > a[max].d) { max = l; }

         if(r < n && a[r].d > a[max].d) { max = r; }

         if(max != i) { swap(a[max], a[i]); }

     }

 }

 void heapsort(int n, pn a[])

 {

     int i = ;

     adjust(n, a);

     for(i = n - ; i > ; i--)

     {

         swap(a[], a[i]);

         adjust(i, a);

     }

 }

 int main()

 {

     int i = , j = ;

     const int m = ;

     const int n = ;

     int ms = , me = ;

     int ts = , te = ;

     int a[m][n] = { {, , , , }, {, , , , }, {, , , , } };

     int cur[m] = {, , }; /* record the current positions of each array which haven't been used */

     pn heap[m] = {pn(, a[][]), pn(, a[][]), pn(, a[][])};

     heapsort(m, heap);

     ms = heap[].d;

     me = heap[m - ].d;

     while(true)

     {

         heapsort(m, heap);

         ts = heap[].d;

         te = heap[m - ].d;

         /* if the current range is smaller than the minimum range */

         if(te - ts < me - ms) { ms = ts; me = te; }

         /* if the sub-array which the smallest element comes from hasn't to the end */

         if(cur[heap[].n] != n)

         {

             heap[].d = a[heap[].n][cur[heap[].n]];

             cur[heap[].n] += ;

         }

         else

         {

             break;

         }

     }

     cout << ms << endl;

     cout << me << endl;

     return ;

 }
以下是自己的思路：

1 每个数组取最后一个值，从这些值当中选出最小值，记为min。

2 遍历每一个数组（min对应的数组返回-1），从中找到第一个大于min的值，再从这些值当中选出最大值。

3 最小区间即为[min, max]。

不知道有没有漏洞？实现以后补上。

巴特西

转：最小区间：k个有序的数组，找到最小区间使k个数组中每个数组至少有一个数在区间中

最新文章

热门文章