LeetCode刷题：找到第K大的元素

本题其实就是考察排序算法，为了减低时间复杂度，所以采用堆排序
 

import java.security.Key;
import java.util.Scanner;public class FindKtopElements {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String line = scanner.nextLine();int k = scanner.nextInt();String[] strArrary = line.split(" ");int[] intArrary = new int[strArrary.length];for (int i=0;i<intArrary.length;i++){intArrary[i] = Integer.parseInt(strArrary[i]);}//todo:排序(升序)int result = k_max(intArrary, k);System.out.print(result);}//使用堆排序实现数组排序private static int k_max(int[] arary, int k) {headSort(arary);return arary[arary.length-k];}private static void headSort(int[] arary) {int n=arary.length;//从最后非叶子节点构建大根堆for(int i=n/2-1;i>=0;i--){headBuild(arary,n,i);}//首尾交换后，从根结点重构大根堆for(int i=n-1;i>0;i--){int temp =arary[0];arary[0]=arary[i];arary[i]=temp;headBuild(arary,i,0);}}//构建大根堆private static void headBuild(int[] arary, int n, int i) {int largest=i;int left=2*i+1;int right=2*i+2;if (left<n && arary[left]>arary[largest]){largest=left;}if (right<n && arary[right]>arary[largest]){largest=right;}if(largest !=i){int temp=arary[i];arary[i]=arary[largest];arary[largest]=temp;headBuild(arary,n,largest);}}}