给定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
两个数,分别为最小区间的左右边界
3 3 2 12 14 2 6 9 4 7 19
2 4
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(); } }
//思路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; }
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); } } }
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;
}
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]
通过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]))