打印N个数组整体最大的Top K

[编程题]打印N个数组整体最大的Top K

热度指数：1980 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有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

[要求]

时间复杂度为 $O(k \log k)$ ，空间复杂度为 $O(k \log k)$

输入描述:

第一行两个整数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

备注:



保证各个输入值合法

算法知识视频讲解

Java

pein531

维护一个容量为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)

Java

牛客196305255号

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)