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

ゝ一世哀愁。 2022-05-29 04:00 198阅读 0赞

![Center][]

import java.util.*;
    //打印N个数组整体最大的Top K
    public class GetTopK{
    	
        //时间复杂度为O(klogN)
        public static void PrintTopK(int[][]matrix,int topK)
        {
        	 int heapSize=matrix.length;
        	 HeapNode[]heap=new HeapNode[heapSize];
        	 for(int i=0;i!=heapSize;i++)
        	 {
        	 	 int index=matrix[i].length-1;
        	 	 heap[i]=new HeapNode(matrix[i][index],i,index);
        	 	 heapInsert(heap,i);
        	 }
        	 System.out.println("TOP"+topK+":");
        	 for(int i=0;i!=topK;i++)
        	 {
        	 	  if(heapSize==0)
        	 	  {
        	 	  	 break;
        	 	  }
        	 	  System.out.print(heap[0].value+" ");
        	 	  if(heap[0].index!=0)
        	 	  {
                       heap[0].value=matrix[heap[0].arrNum][--heap[0].index];
        	 	  }else{
    
        	 	  	 swap(heap,0,--heapSize);
        	 	  }
        	 	  heapify(heap,0,heapSize);
        	 }
    
        }
        //建堆的过程
        public static void heapInsert(HeapNode[]heap,int index)
        {
        	while(index!=0)
        	{
    
              int parent=(index-1)/2;
              if(heap[parent].value<heap[index].value)
              {
                   swap(heap,parent,index);
                   index=parent;
              }else{
              	break;
              }
    
        	}      
        }
        //堆的调整
        public static void heapify(HeapNode[]heap,int index,int heapSize)
        {  
               int left=index*2+1;
               int right=index*2+2;
               int largest=index;
               while(left<heapSize){
    
               	  if(heap[left].value>heap[index].value)
               	  {
               	  	 largest=left;
               	  }
               	  if(right<heapSize&&heap[right].value>heap[largest].value)
               	  {
               	  	 largest=right;
               	  }
               	  if(largest!=index)
               	  {
               	  	 swap(heap,largest,index);
               	  }else{
               	  	  break;
               	  }
               	  index=largest;
               	  left=index*2+1;
               	  right=index*2+2;
    
               }
    
        }
    
        //数据的交换
        public static void swap(HeapNode[]arr,int index1,int index2)
        {
        	HeapNode temp=arr[index1];
        	arr[index1]=arr[index2];
        	arr[index2]=temp;
        }
    
        //生成随机的矩阵
       public static int[][] generateRandomMatrix(int maxRow, int maxCol,
    			int maxValue) {
    		if (maxRow < 0 || maxCol < 0) {
    			return null;
    		}
    		int[][] matrix = new int[(int) (Math.random() * maxRow) + 1][];
    		for (int i = 0; i != matrix.length; i++) {
    			matrix[i] = new int[(int) (Math.random() * maxCol) + 1];
    			for (int j = 0; j != matrix[i].length; j++) {
    				matrix[i][j] = (int) (Math.random() * maxValue);
    			}
    			Arrays.sort(matrix[i]);
    		}
    		return matrix;
    	}
        //打印矩阵
    	public static void printMatrix(int[][] matrix) {
    		for (int i = 0; i != matrix.length; i++) {
    			for (int j = 0; j != matrix[i].length; j++) {
    				System.out.print(matrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    		System.out.println();
    	}
    	public static void main(String[]args)
    	{
    		System.out.println("输入三个数(最大行,最大列，最大值)");
    		Scanner sin=new Scanner(System.in);
    		int []arr=new int[3];
    		for(int i=0;i<arr.length;i++)
    		{
    			arr[i]=sin.nextInt();
    		}
    		System.out.println();
            int[][]matrix=generateRandomMatrix(arr[0],arr[1],arr[2]);
            printMatrix(matrix);
            System.out.println("===========================");
    		PrintTopK(matrix, 100);
    		
    
    
    	}
    }
    
    //堆结点的定义
    class HeapNode{
    
        public int value; //值
        public int arrNum; //来自的数组
        public int index; //来自数组的哪个位置
    
        public HeapNode(int value,int arrNu,int index)
        {
        	this.value=value;
        	this.arrNum=arrNu;
        	this.index=index;
        }
    
    }

![Center 1][]

[Center]: /images/20220529/e6c1a2cf092a411d8512d48f302b3272.png
[Center 1]: /images/20220529/47afcfdef2c94261880492a7ec2690ae.png