有N个长度不一的数组，所有的数组都是有序的，请从大到小打印这N个数组整体最大的前K个数。
例如，输入含有N行元素的二维数组可以代表N个一维数组。
219, 405, 538, 845, 971
148, 558
52, 99, 348, 691
再输入整数k=5，则打印：
Top 5: 971, 845, 691, 558, 538
[要求]
时间复杂度为)
，空间复杂度为
[编程题]打印N个数组整体最大的Top K
- 热度指数：1994 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行两个整数T, K。分别表示数组个数，需要打印前K大的元素
接下来T行，每行输入格式如下：
开头一个整数N，表示该数组的大小，接下来N个已排好序的数表示数组内的数
输出描述:
从大到小输出输出K个整数，表示前K大。
示例1
输入
3 5 5 219 405 538 845 971 2 148 558 4 52 99 348 691
输出
971 845 691 558 538
备注:
保证各个输入值合法
**题目，测试用例是错的。
提交后提示检查数组越界和非法访问。我仔细检查了n遍没有发现错误，然后去查找别人的代码，发现和我的思路差不多。
老子难受的一批，我非要给他弄明白怎么回事。我把别人正确的代码慢慢改成和我的代码相似的代码，一边修改一边验证。搞了很久发现能ac的代码和我的代码没有本质区别，只不过他在读取每一行数据时把第一个数值也记录到二维数组中，本人没有记录。就tm这个问题能导致我出错？我很不爽，一定要把罪魁祸首揪出来，mb的牛客不提供完整的测试用例（实际在报错的时候屁都没有，就提示检查数组越界和非法访问，点击查看结果对比依然是屁都没有），我在学习算法又不是考试，你把测试用例藏起来干嘛？你干嘛不把别人正确代码给隐藏起来？弄了好久，期间还去LeetCode上搜这题，发现没有这题。mlgbd气的老子火冒三丈，骂了个*****。
吃了顿饭后接着搞，最后实在是没辙了，怀疑是测试用例有问题，在别人正确代码中添加了一句代码，然后发现系统报错了。
if (m == 1)// m表示读取一行数据split后得到的数组长度。
throw new RuntimeException("cnm"); 终于找到问题了。不是在备注里写明了数组内总个数大于1。你备注个是个锤子。我现在看到牛客报数组越界或非法访问就恶心。 本来一道20min以内解决的问题，最后测试用例有问题，本人比较爱较真（1.***非要证明是你牛客错了；2.牛客的提示“报数组越界和非法访问”让我觉得恶心，啥也看不到。）
本来一天没干事就慌得一批，又搞了几个小时，肝都要气炸了。 。。
我的代码如下：把注释取消就能ac。
import java.io.*;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int n = Integer.valueOf(s[0]);
int k = Integer.valueOf(s[1]);
int[][] arr = new int[n][];
for (int i = 0; i < n; i++) {
String[] str = reader.readLine().split(" ");
int m = str.length;
arr[i] = new int[m - 1];
for (int j = 0; j < m - 1; j++) {
arr[i][j] = Integer.valueOf(str[j + 1]);
}
}
PriorityQueue<Tuple> maxHeap = new PriorityQueue<>((o1, o2) -> o2.val - o1.val);
for (int i = 0; i < n; i++) {
int len = arr[i].length;
//在这里设置 len==0，直接continue，就是能ac的代码。 //if(len == 0) continue;
maxHeap.offer(new Tuple(i, len - 1, arr[i][len - 1]));
}
StringBuilder res = new StringBuilder();
for (int j = 0; j < k; j++) {
Tuple temp = maxHeap.poll();
res.append(temp.val).append(" ");
if (temp.index > 0) {
maxHeap.add(new Tuple(temp.line, temp.index - 1, arr[temp.line][temp.index - 1]));
}
}
System.out.println(res);
}
static class Tuple {
int line;
int index;
int val;
Tuple(int line, int index, int val) {
this.line = line;
this.index = index;
this.val = val;
}
}
} 这是我为了比对我的代码错哪里而去修改的别人的代码产物，发现就第一个for循环处不一样。
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
int n = Integer.valueOf(s[0]);
int k = Integer.valueOf(s[1]);
int[][] arr = new int[n][];
for (int i = 0; i < n; i++) {
String[] str = reader.readLine().split(" ");
int m = str.length;
arr[i] = new int[m];
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.valueOf(str[j]);
}
}
PriorityQueue<Tuple> maxHeap = new PriorityQueue<>((o1, o2) -> o2.val - o1.val);
for (int i = 0; i < n; i++) {
int len = arr[i].length;
maxHeap.offer(new Tuple(i, len - 1, arr[i][len - 1]));
}
StringBuilder res = new StringBuilder();
for (int j = 0; j < k; j++) {
Tuple temp = maxHeap.poll();
res.append(temp.val).append(" ");
if (temp.index > 1) {
maxHeap.add(new Tuple(temp.line, temp.index - 1, arr[temp.line][temp.index - 1]));
}
}
System.out.println(res);
}
static class Tuple {
int line;
int index;
int val;
Tuple(int line, int index, int val) {
this.line = line;
this.index = index;
this.val = val;
}
}
} 难过的一天，希望别人看到能解决问题，不要像我这么较真，一点收获都没，白费几小时。
编辑于 2020-06-06 22:59:31
回复(6)
维护一个容量为k的小根堆，每次淘汰堆顶的小数，往堆中不断放大数就行
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int t = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
while(t-- > 0){
params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]);
int[] arr = new int[n];
for(int i = 0; i < n; i++){
int num = Integer.parseInt(params[i + 1]);
if(minHeap.size() < k){
minHeap.offer(num);
}else{
if(minHeap.peek() < num){
minHeap.poll();
minHeap.offer(num);
}
}
}
}
int[] res = new int[k];
for(int i = k - 1; i >= 0; i--) res[i] = minHeap.poll();
for(int i = 0; i < k; i++) System.out.print(res[i] + " ");
}
}
发表于 2021-11-13 21:49:10
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int T,K,n,x;
cin>>T>>K;
priority_queue<int, vector<int>, greater<int>> q;
for(int i=0;i<T;i++){
cin>>n;
for(int j=0;j<n;j++){
cin>>x;
if(q.size() < K)
q.push(x);
else{
q.pop();
q.push(x);
}
}
}
int l = q.size();
int a[l];
for(int i=0;i<l;i++){
a[l-i-1] = q.top();
q.pop();
}
for(int i=0;i<l;i++)
cout<<a[i]<<" ";
return 0;
}
发表于 2020-02-25 00:30:43
回复(0)
#include<bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
// 递归打印
void print() {
if (pq.empty()) return;
int val = pq.top();
pq.pop();
print();
printf("%d ", val);
}
int main() {
int T, K;
scanf("%d%d", &T, &K);
int len = 0;
int x = 0;
int psize = 0; //记录最小堆的大小
while (T--) {
scanf("%d", &len);
while (len--) {
scanf("%d", &x);
if (psize < K) {
psize++;
pq.push(x);
} else {
pq.pop();
pq.push(x);
}
}
}
print();
return 0;
}
发表于 2019-08-02 09:34:51
回复(2)
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class HeapNode{
public:
int val;
int arrayId;
HeapNode(int v,int arrId):val(v),arrayId(arrId){}
bool operator<(const HeapNode& another)const{
return val < another.val;
}
};
int main() {
int T,K;
cin >> T >> K;
vector<vector<int>> arrs(T);
for(int i = 0;i < T;i++){
int n = 0;
cin >> n;
arrs[i].resize(n);
for(int j = 0;j < n;j++){
cin >> arrs[i][j];
}
}
priority_queue<HeapNode> heap;
for(int i = 0;i < T;i++){
if(arrs[i].empty()) continue;
heap.push(HeapNode(arrs[i].back(),i));
arrs[i].pop_back();
}
for(int i = 0;i < K;i++){
cout << heap.top().val << " ";
int arrId = heap.top().arrayId;
heap.pop();
if(arrs[arrId].empty()) continue;
heap.push(HeapNode(arrs[arrId].back(),arrId));
arrs[arrId].pop_back();
}
}
C++利用STL库实现的堆容器的实现
发表于 2024-02-27 21:53:14
回复(0)
import java.util.*;
//记录加入堆中的每一个数来自哪个数组，值，与位置
class HeapNode {
public int val;
public int arrNum;
public int index;
public HeapNode(int v, int a, int i) {
this.val = v;
this.arrNum = a;
this.index = i;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[][] m = new int[n][];
for (int i = 0; i < n; i++) {
int n2 = sc.nextInt();
int[] arr = new int[n2];
for (int j = 0; j < n2; j++) {
arr[j] = sc.nextInt();
}
m[i] = arr;
}
int[] res = getTopK(m, k);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.length; i++) {
sb.append(res[i] + " ");
}
System.out.println(sb.toString());
sc.close();
}
//建一个长度为n的大根堆，最开始装所有数组的最后位置（因为是有序数组），
//然后把头弹出，必为所有数的最大值。然后找第二大的数时，前一个是从
//哪个数组弹出的，就把弹出位置的前一个数也就是arr[len-2]加进大根堆
//头，用heapify，以此类推.
//若某一弹出数为该数组的第一个位置，则置换其与最后一个数，同时有效长度--。
public static int[] getTopK(int[][] m, int k) {
//长度为n的大根堆
int validArrNum = 0;
int len = 0;
//防止k比总数量大，或者某一行长度为0
for (int i = 0; i < m.length; i++) {
if (m[i] != null && m[i].length != 0)
validArrNum++;
len += m[i].length;
}
HeapNode[] heap = new HeapNode[validArrNum];
len = len <= k ? len : k;
int[] res = new int[len];
int heapI = 0;
for (int i = 0; i < m.length; i++) {
if (m[i] == null || m[i].length == 0)
continue;
int index = m[i].length-1;
heap[heapI] = new HeapNode(m[i][index], i, index);
heapInsert(heap, heapI++);
}
int size = validArrNum;
for (int i = 0; i < len; i++) {
res[i] = heap[0].val;
int arrNum = heap[0].arrNum;
int index = heap[0].index;
if (index > 0) {
heap[0] = new HeapNode(m[arrNum][index-1], arrNum, index-1);
heapify(heap, 0, size);
}
else {
heap[0] = heap[heap.length-1];
heapify(heap, 0, --size);
}
}
return res;
}
public static void heapInsert(HeapNode[] arr, int i) {
while (arr[(i-1)/2].val < arr[i].val) {
swap(arr, (i-1)/2, i);
i = (i-1)/2;
}
}
public static void swap(HeapNode[] arr, int i, int j) {
HeapNode tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void heapify (HeapNode[] arr, int i, int size) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int maxI = 0;
while (left < size) {
maxI = left;
if (right < size)
maxI = arr[left].val < arr[right].val ? right : maxI;
maxI = arr[maxI].val < arr[i].val ? i : maxI;
if (maxI == i)
break;
swap(arr, i, maxI);
i = maxI;
left = 2 * i + 1;
right = 2 * i + 2;
}
}
}
编辑于 2021-08-21 22:39:29
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[][] arr=new int[n][];
int[] pos=new int[n];
int k=sc.nextInt();
for(int i=0;i<n;i++){
int tmp=sc.nextInt();
int[] A=new int[tmp];
pos[i]=tmp-1;
for(int j=0;j<tmp;j++){
A[j]=sc.nextInt();
}
arr[i]=A;
}
solve(arr,pos,k);
}
sc.close();
}
public static void solve(int[][] arr,int[] pos,int k) {
StringBuilder sb=new StringBuilder();
for(int i=0;i<k;i++) {
int tmp=arr[0][pos[0]];
int index=0;
for(int j=1;j<arr.length;j++) {
if(pos[j]>0&&arr[j][pos[j]]>tmp) {
tmp=arr[j][pos[j]];
index=j;
}
}
pos[index]--;
sb.append(tmp).append(" ");
}
System.out.println(sb.toString().trim());
}
}
发表于 2021-03-09 15:36:35
回复(0)
#include <cstdio>
(802)#include <cstring>
#include <algorithm>
(831)#include <iostream>
#include <string>
(765)#include <vector>
#include <stack>
(850)#include <bitset>
#include <cstdlib>
(895)#include <cmath>
#include <set>
(855)#include <list>
#include <deque>
(2572)#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
struct HeapNode
{
int val;
int row;
int col;
bool operator<(const HeapNode &a) const
{
return this->val < a.val;
}
bool operator>(const HeapNode &a) const
{
return this->val > a.val;
}
};
int main()
{
int t, k;
scanf("%d%d\n", &t, &k);
vector<vector<int>> arr2d;
for (int i = 0; i < t; i++)
{
int n;
scanf("%d", &n);
vector<int> arr;
for (int j = 0; j < n; j++)
{
int val;
scanf("%d", &val);
arr.push_back(val);
}
arr2d.push_back(arr);
}
priority_queue<HeapNode, vector<HeapNode>> queue;
for (int i = 0; i < t; i++)
{
if (!arr2d[i].empty())
{
HeapNode node;
node.val = arr2d[i].back();
node.row = i;
node.col = arr2d[i].size() - 1;
queue.push(node);
}
}
for (int i = 0; i < k; i++)
{
HeapNode node = queue.top();
cout << node.val << " ";
if (node.col > 0)
{
HeapNode next;
next.val = arr2d[node.row][node.col -1];
next.row = node.row;
next.col = node.col - 1;
queue.pop();
queue.push(next);
}
else
{
queue.pop();
}
}
cout << endl;
return EXIT_SUCCESS;
} 1. 感觉楼上都有点投机取巧 相当于在O(n^2)的遍历中进行输出，不符合题目的 O(klogk)要求
2. 空行真恶心
发表于 2020-03-17 12:04:59
回复(3)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
PriorityQueue<Integer> queue = new PriorityQueue<>((n1,n2)->n1-n2) ;
for(int i=0;i<n;i++) {
int p = scanner.nextInt();
for(int j=0;j<p;j++) {
queue.add(scanner.nextInt());
if(queue.size()>k) {
queue.poll();
}
}
}
int[] arr = new int[k];
for(int i=0;i<k;i++) {
arr[i] = queue.poll();
}
for(int i=k-1;i>=0;i--) {
System.out.print(arr[i] + " ");
}
}
}
发表于 2019-10-24 17:20:52
回复(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
