查找第K大的元素

题目描述：

查找第K大的元素_牛客网
给定一个无序的整型数组A[n],数组大小大于等于3,允许有值相同的元素;请设计算法找到该数组排序后第三大的元素值并输出.

输入描述：

一个非空的整数数组(至少有3个元素,可正可负)

输出描述：

第三大的元素值

输入示例1：

[1,2,3,4,5]

输出示例1：

3

输入示例2：

[1,1,2,2,3]

输出示例2：

2

输入示例3：

[6,5,4,4,1,2]

输出示例3：

4

题目分析：

这道题呢，查找第K大的元素，采用了最小堆的方式实现，维持堆大小为K，堆顶元素即为所求元素。具体代码如下~

代码实现：

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        str=str.replace("[","").replace("]","");
        String[] stra=str.split(",");
        int[] nums=new int[stra.length];
        for(int i=0;i<stra.length;i++){
            nums[i]=Integer.parseInt(stra[i]);
        }
        System.out.println(Kth(nums,3));

    }
    public static int Kth(int[] nums,int k){
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        for(int i : nums){
            minHeap.add(i);
            if(minHeap.size()>k)
                minHeap.poll();
        }
        return minHeap.peek();
    }
}