首页 > 试题广场 >

最小区间

[编程题]最小区间
  • 热度指数:1475 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给定k个有序数组, 每个数组有个N个元素,找出一个最小的闭区间,使其包含每个数组中的至少一个元素。 
给定两个区间[a,b], [c,d]: 
如果 b-a < d-c,则认为[a, b]是更小的区间;
如果 b-a == d-c,且a < c,则认为[a, b]是更小的区间。

输入描述:
K
N
x11 x12 x13 ... x1n
...
xk1 xk2 xk3 ... xkn


输出描述:
两个数,分别为最小区间的左右边界
示例1

输入

3
3
2 12 14
2 6 9
4 7 19

输出

2 4
首先,这道题看上去就会让人想到多路归并,多路归并中用到的主要组件就是优先队列。
在这个问题中依旧可以用优先队列。
从优先队列中依次弹出元素,把弹出的元素放到另一个“组件”里面,这个组件有如下特性:
  1. 是一个队列,容纳从优先队列里面弹出来的元素
  2. 因为优先队列是有序的,所以这个容器也是有序的
  3. 对于这个队列,如果队首的元素不能充分代表它所在的数组(K个数组中的一个),那么这个队首元素就应该出队了
这个容器是什么呢?单调队列。
单调队列还需要一个辅助数组inqCount,inqCoount[i]表示第i个数组在队列中的元素的个数,这个数组用来出队。
每次入队之后,执行:弹出队首元素、计算区间(区间就是单调队列的队首和队尾组成的区间)。


import java.util.*;  public class Main { class Point { int x, k, index;   Point(int x, int k, int index) {  this.x = x;  this.k = k;  this.index = index; }
} Main() {
    Scanner cin = new Scanner(System.in);  int K = cin.nextInt();  int N = cin.nextInt();    PriorityQueue<Point> q = new PriorityQueue<>(Comparator.comparing(x -> x.x));  for (int i = 0; i < K; i++) { for (int j = 0; j < N; j++) { int x = cin.nextInt();  q.add(new Point(x, i, j));  }
    }  int[] inqCount = new int[K];    Queue<Point> qq = new LinkedList<>();//单调队列    int nonzeroCount = 0;  int ans = Integer.MAX_VALUE;  int beg = 0, end = 0;  boolean startCheck = false;//是否开始覆盖    while (!q.isEmpty()) {
        Point now = q.poll();    qq.add(now);    inqCount[now.k]++;  if (inqCount[now.k] == 1) {
            nonzeroCount++;  if (nonzeroCount == K) {
                startCheck = true;  }
        } //弹出无用元素    while (!qq.isEmpty() && inqCount[qq.peek().k] > 1) {
            inqCount[qq.peek().k]--;  qq.poll();  }  if (startCheck) { int minValue = qq.peek().x;  int nowAns = now.x - minValue;  if (nowAns < ans) {
                ans = nowAns;  beg = minValue;  end = now.x;  }
        }
    }
    System.out.println(beg + " " + end); } public static void main(String[] args) { new Main(); }
}
编辑于 2020-06-21 14:03:43 回复(0)
WAK头像 WAK
通过90%,提示超时
思路1:首先把K个数组中的元素多路归并按升序排成一个数组,保留值和原数组信息。然后通过两个指针begin和end从位置0开始动态得向后移动,判断begin和end之间是否满足包含每个数组至少一个元素,若满足,则begin后移,若不满足,则end后移,直到begin和end到数组尾部。在条件满足的情况下,维护一个start、final、length,作为最后的结果输出。

AC,将多路归并中的比较用优先队列实现,将O(k)改为O(logk),解决超时问题
//思路1
#include<bits/stdc++.h> using namespace std; struct pt{     int x;     int pos;     pt(int a,int b):x(a),pos(b){} }; int main(){     int k,n;     while(cin>>k>>n){         vector<vector<int>>all; //原始数据         vector<int> vec; //多路归并时,每个数组中的位置         for(int i = 0;i<k;i++){             vector<int>temp;             for(int j = 0;j<n;j++){                 int x;                 cin>>x;                 temp.push_back(x);             }             all.push_back(temp);             vec.push_back(0);         }         vector<pt> sort; //多路归并后的有序数组,保存值和原数组信息         int sum = 0;         while(sum!=k*n){ //多路归并             int min = INT_MAX;             int pos = 0;             for(int i = 0;i<vec.size();i++){                 if(vec[i]<n&&all[i][vec[i]]<min){                     min = all[i][vec[i]];                     pos = i;                 }             }             vec[pos]++;             pt temp(min,pos);             sort.push_back(temp);             sum++;         }         for(int i = 0;i<vec.size();i++)             vec[i] = 0; //保存动态范围内含有各数组值的个数         int begin = 0; //动态范围左         int end = 0; //动态范围右         int start = 0; //符合条件的范围左         int final = 0; //符合条件的范围右         int length = INT_MAX; //符合条件的最短长度         bool flg = false;         vec[sort[0].pos]++;         while(begin<sort.size()-1||end<sort.size()-1){             bool flgg = true;             for(int i = 0;i<k;i++)                 flgg = flgg&&(vec[i]>=1); //判断是否满足包含每个数组至少一个元素             if(!flgg&&end<sort.size()){ //不满足,end++                 if(end<sort.size()-1)                     end++;                 vec[sort[end].pos]++;                               }             if(!flgg&&end==sort.size()-1) //不满足且end到尾部,跳出循环                 break;             if(flgg&&begin<sort.size()){ //满足,begin++                 int x = sort[end].x-sort[begin].x;                 if(x<length){ //更新start,final,length                     start = sort[begin].x;                     final = sort[end].x;                     length = x;                 }                 vec[sort[begin].pos]--;                 if(begin<sort.size()-1)                     begin++;             }             int a = 1;         }         cout<<start<<" "<<final<<endl; //输出结果     }     system("pause");     return 0; }
//思路2,用优先队列去实现多路归并
#include<bits/stdc++.h> using namespace std; struct pt{     int x;     int pos;     pt(int a,int b):x(a),pos(b){} }; struct cmp{ //重写比较函数     bool operator()(const pt a,const pt b){         return a.x>b.x;     } }; int main(){     int k,n;     while(cin>>k>>n){         vector<vector<pt>>all;         vector<int> vec;         for(int i = 0;i<k;i++){             vector<pt>temp;             for(int j = 0;j<n;j++){                 int x;                 cin>>x;                 pt p(x,i);                 temp.push_back(p);             }             all.push_back(temp);             vec.push_back(0);         }         vector<pt> sort;         priority_queue<pt,vector<pt>,cmp> qu; //优先队列         for(int i = 0;i<k;i++)             qu.push(all[i][0]);         while(!qu.empty()){             pt temp = qu.top();             qu.pop();             sort.push_back(temp);             vec[temp.pos]++;             if(vec[temp.pos]<=n-1){                 qu.push(all[temp.pos][vec[temp.pos]]);             }         }         for(int i = 0;i<vec.size();i++)             vec[i] = 0;         int begin = 0;         int end = 0;         int start = 0;         int final = 0;         int length = INT_MAX;         bool flg = false;         vec[sort[0].pos]++;         while(begin<sort.size()-1||end<sort.size()-1){             bool flgg = true;             for(int i = 0;i<k;i++)                 flgg = flgg&&(vec[i]>=1);             if(!flgg&&end<sort.size()){                 if(end<sort.size()-1)                     end++;                 vec[sort[end].pos]++;             }             if(!flgg&&end==sort.size()-1)                 break;             if(flgg&&begin<sort.size()){                 int x = sort[end].x-sort[begin].x;                 if(x<length){                     start = sort[begin].x;                     final = sort[end].x;                     length = x;                 }                 vec[sort[begin].pos]--;                 if(begin<sort.size()-1)                     begin++;             }             int a = 1;         }         cout<<start<<" "<<final<<endl;     }     system("pause");     return 0; }


编辑于 2018-08-16 20:02:31 回复(0)
import java.util.Scanner;

/**
 * Created by SeanSeanSean on 2018/8/17.
 * 商汤科技
 * 最小区间 
  * 直接最笨的方法,每次把最小的那个数往前推一个,计算相差值,若比之前小进行记录。
 */
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int k = sc.nextInt();
            int n = sc.nextInt();
            int[][] array = new int[k][n];
            for (int i = 0; i < k; i++){
                for (int j = 0; j < n; j++){
                    array[i][j] = sc.nextInt();
                }
            }
            int[] loc = new int[k];
            int[] val = new int[k];
            for (int i = 0; i < k; i++){
                loc[i] = 0;
                val[i] = array[i][loc[i]];
            }
            int temp = Integer.MAX_VALUE;
            int down = 0;
            int up = 0;

            while (true){
                int max_val = Integer.MIN_VALUE;
                int min_val = Integer.MAX_VALUE;
                int max_loc = -1;
                int min_loc = -1;
                for (int i = 0; i < k; i++){
                    if(val[i] > max_val) {
                        max_val = val[i];
                        max_loc = i;
                    }
                    if(val[i] < min_val){
                        min_val = val[i];
                        min_loc = i;
                    }
                }
                if(max_val - min_val < temp){
                    down = min_val;
                    up = max_val;
                    temp = max_val-min_val;
                }
                loc[min_loc]++;
                if (loc[min_loc] == n){
                    break;
                }
                else
                    val[min_loc] = array[min_loc][loc[min_loc]];
            }
            System.out.println(down + " " + up);
        }
    }
}

发表于 2018-08-17 15:16:51 回复(0)

k个数组成小顶堆,堆顶元素是哪一行的就用那一行的下一个值替换堆顶,堆调整,直到有一行查到了最后结束

#include <bits/stdc++.h>
using namespace std;

//小顶堆 第一个元素最小值 输出是从大到小,因为每次调整堆将堆顶和下面的交换
//* 堆调整算法。(小顶堆)
//* 已知heap[top]结点的左右子树均为堆,调整堆中元素,使以heap[top]为根结点的树为堆。
//* n为堆中元素总数。
//A是原数组 B是原数组对应序列
void HeapAdjust(int *A, int *B, int s, int m)
{
    int j, rc = A[s], rc2 = B[s];
    for (j = 2 * s + 1; j <= m; j = 2 * j + 1)
    {
        if (j < m && A[j] > A[j + 1])
            j++;    //使j指向左右孩子中较小的结点。
        if (A[j] > rc)
            break;
        A[s] = A[j];
        B[s] = B[j];
        s = j;
    }
    A[s] = rc;
    B[s] = rc2;
}

int getMax(int data[], int n)
{
    int maxvalue = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        if (data[i] > maxvalue)
        {
            maxvalue = data[i];
        }
    }
    return maxvalue;
}

int main()
{
    int k, n;
    cin >> k >> n;
    if (!k || !n)
        return 0;

    //data[i][0]存放每个数组的索引
    int **data = new int*[k];
    for (int i = 0; i < k; i++)
        data[i] = new int[n + 1];

    int *data2 = new int[k];//k个数组每个数字一个元素,形成区间
    int *data2Index = new int[k];//每个元素所属数组行数
    int maxValue = 0, maxIndex;

    for (int i = 0; i < k; i++)
    {
        data[i][0] = 1;//初始指向每个数组第一个元素
        for (int j = 1; j < n + 1; j++)
        {
            cin >> data[i][j];
            //初始化区间数组
            if (j == 1)
            {
                data2Index[i] = i;
                data2[i] = data[i][j];
                if (data2[i] > maxValue)
                {
                    maxValue = data2[i];
                    maxIndex = i;
                }
            }    
        }
    }

    //建最小堆
    for (int i = k / 2 - 1; i >= 0; --i)
        HeapAdjust(data2, data2Index, i, k - 1);

    int left = INT_MAX, right = INT_MIN, minLength = INT_MAX;
    int minIndex, tleft, tright;
    while (1)
    {
        HeapAdjust(data2, data2Index, 0, k - 1);

        tleft = data2[0];
        tright = maxValue;
        minIndex = data2Index[0];

        //满足条件
        if ((tright - tleft < minLength) || (tright - tleft == minLength && tleft < left))
        {
            minLength = tright - tleft;
            left = tleft;
            right = tright;
        }

        //约束条件
        if (++data[minIndex][0] > n)
            break;

        data2[0] = data[minIndex][data[minIndex][0]];
        //如果替换掉的刚好是原来data2中的最大值,重新找最大值
        if (data2[0] > maxValue)
            maxValue = data2[0];
        if (data2[0] <= maxValue && maxIndex == 0)
            maxValue = getMax(data2, k);
    }
    cout << left << " " << right;

    return 0;
}
编辑于 2018-08-19 17:06:11 回复(0)
  • map记录元素值到元素所属数组的映射
  • 按元素值遍历map,双指针维护当前最小可行区间
  • 复杂度
发表于 2021-03-10 11:47:09 回复(0)
思路: 将所有数组合并成一个数组mergeArr, 由数组有序即可得到mergeArr最小数与最大数形成的区间符合要求,然后分别缩小两端的数组以求得最小区间。
function searchMinRange(obj) {
    function mergeJuddge(start, end) {
        let textFunc = '';
        let propetyArr = Object.getOwnPropertyNames(obj);
        propetyArr.forEach((item, index) => {
            if(propetyArr[index + 1]) {
                textFunc += `isContain([${obj[item]}], ${start}, ${end}) &&`;
            } else {
                textFunc += `isContain([${obj[item]}], ${start}, ${end})`;
            }
        })
        return !eval(textFunc);
    }
    // 判断数组是否有包含 闭区间的元素
     function isContain(arr, start, end) {
         let result = arr.find( item => {
             return item >= start && item <= end;
     });
         return result === undefined ? false : true; // 避免result为 0 时被解析为false
     }

      // 思路: 将所有数组合并成一个数组mergeArr, 由数组有序即可得到mergeArr最小数与最大数形成的区间符合要求
      // 然后将该区间缩小,逐步得出最小区间
      var mergeArr = [];
      for(let key in obj) {
          mergeArr = mergeArr.concat(obj[key]);
      };
      mergeArr = [...new Set(mergeArr)];

      var resultStart = 0;
      var resultEnd = 0;  // 用来记录区别的上下限

            
       // 先缩小上限的范围
       for(let i = mergeArr.length -2;i >= 0; i--) {
           let start = mergeArr[0];
           let end = mergeArr[i];
           if( mergeJuddge(start, end) ) {
               resultEnd = mergeArr[i + 1];
             
           }
       }
            // 在缩小下限
    for(let i = 0;i < mergeArr.length; i++) {
        let start = mergeArr[i];
        if( mergeJuddge(start, resultEnd) ) {
            resultStart = mergeArr[i - 1];
            break;
        }
    }
    return `最小闭区间为 [${resultStart}, ${resultEnd}]`;
}
var obj = {
    a: [1,2,3],
    b: [3,4,5],
    c: [7,8,9],
    d: [7,8,9,10,11],
    e: [10,11,12]
}
searchMinRange(obj); // 最小闭区间为 [3, 10]


发表于 2019-08-19 15:18:12 回复(0)
用优先队列做的
import java.util.*;

public class Main {
    static class Node {
        int num;
        int index;
        int value;
        public Node(int num, int index, int value){
            this.index = index;
            this.num = num;
            this.value = value;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int n = in.nextInt();
        ArrayList<ArrayList<Node>> lists = new ArrayList<ArrayList<Node>>();
        for(int i = 0; i < k; i++){
            ArrayList<Node> list = new ArrayList<>();
            for(int j = 0; j < n; j++){
                int tmp = in.nextInt();
                Node node = new Node(i,j,tmp);
                list.add(node);
            }
            lists.add(list);
        }
        int []range = new int[2];
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.value-o2.value;
            }
        });
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        for(int i = 0; i < lists.size(); i++){
            ArrayList<Node> list = lists.get(i);
            if(list != null) {
                if(list.get(0).value < left){
                    left = list.get(0).value;
                }
                if(list.get(0).value>right){
                    right = list.get(0).value;
                }
                pq.offer(list.get(0));
            }
        }
        range[0] = left;
        range[1] = right;
        while(!pq.isEmpty()){
            Node s = pq.poll();
            int num = s.num;
            int index = s.index;
            if( index +1 < n ){
                pq.offer(lists.get(num).get(index+1));
                left = pq.peek().value;
                right =  Math.max(lists.get(num).get(index+1).value,right);
                if(right - left < range[1]-range[0]){
                    range[0] = left;
                    range[1] = right;
                }

            } else{
                break;
            }
        }
        System.out.println(range[0]+" "+range[1]);


    }
}

发表于 2019-08-18 11:52:54 回复(0)
python只有60%.。。。
k = int(input())
n = int(input())
def mergesort(l,r,index):
    res=[]
    i,j = 0,0
    while i<len(l) and j<len(r):
        if l[i][0]<r[j]:
            res.append(l[i])
            i+=1
        else:
            res.append([r[j],index])
            j+=1
    res+=l[i:]
    while j<len(r):
        res.append([r[j],index])
        j+=1
    return res

index = 0
mtx = map(int,raw_input().split())
mtx_index = [[w,index] for w in mtx]
mids = []
for i in range(k-1):
    x = map(int,raw_input().split())
    index += 1 
    mtx_index = mergesort(mtx_index,x,index)
left, right = 0, k-1
a = set(range(k))
result = []
pos = 0
while left<right and right<len(mtx_index):
    set_l_r = set([w[1] for w in mtx_index[left:right+1]])
    #print set_l_r
    if a == set_l_r:
        result.append([mtx_index[left][0],mtx_index[right][0],mtx_index[right][0]-mtx_index[left][0]])
        if right-left+1 == k:
            pos = 1
            #print 'pos=1'+'\n',right,'-',left,'=',mtx_index[left][0],mtx_index[right][0]
            print mtx_index[left][0],mtx_index[right][0]
            break
        left+=1
    else:right+=1
if pos == 0:
    min_index = min([w[2] for w in result])
    for i in range(len(result)):
        if result[i][2] == min_index:
            print result[i][0],result[i][1]
            break

发表于 2018-10-15 11:12:27 回复(0)

通过50%,提示超时

K = int(input())
N = int(input())
data = []
data1 = []
for i in range(K):
    g = input().split(" ")
    d = [int (j) for j in g]
    data.append(d)
for i in data:
    for j in i:
        data1.append(j)

data1 = set(data1)
data1 = list(data1)
data1.sort()
start = 0
end = 0
edge = len(data1)
s = 0
e = 0
M = []
def findMin():
    m = data[0][0]
    for i in data:
        mi = min(i)
        if mi<m:
            m = mi
    return m
def getD(j,s,e):
    if s<=j<=e:
        return 1
    else:
        return 0

def isMin(s,e):
    num = 0;
    for i in data:
        for j in i:
            r = getD(j,s,e)
            if r == 1:
                break
        if r == 0:
            return 0
    return 1

def getMin(data):

    m= data[0]
    i = 1
    l = len(data)
    while i < l:
        if (m[1] - m[0]) == (data[i][1] - data[i][0]) and m[0] < data[i][0]:
            i+=1
            continue

        elif (m[1] - m[0]) < (data[i][1] - data[i][0]):
            i+=1
            continue
        else:
            m = data[i]
            i+=1
    return m
start = end = data1.index(findMin())                     
while end+1 != edge:
    s = data1[start]
    e = data1[end]
    r = isMin(s,e)
    if r == 1:
        M.append([s,e])
        start +=1
    else:
        end += 1
start += 1
while start <= end:
    s = data1[start]
    e = data1[end]
    r = isMin(s,e)
    if r == 1:
        M.append([s,e])
        start +=1
    else:
        break

re = getMin(M)
print("{0} {1}".format(re[0],re[1]))
发表于 2018-08-29 10:50:46 回复(0)