topk问题问题

方法1 -- 利用小根堆

维护一个k大小的最小堆（每次出堆的元素是堆中最小的元素）, 然后把剩下的元素依次与堆顶进行比较, 如果大于堆顶就舍弃堆顶元素把更大的元素作为新堆顶, 然后继续维护小根堆。

• 时间复杂度O(n*logk)
• 空间复杂度O(k)

import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Queue;
import static java.lang.Integer.parseInt;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().replace("[", "").replace("]","").split(",");
        int [] arr = new int[str.length];
        for(int i = 0; i < arr.length; i++){
            arr[i] = parseInt(str[i]);
        }

        // PriorityQueue维护小根堆，保证每次出队的元素最小。
        //Queue<Integer> heap = new PriorityQueue<>(3);
        PriorityQueue<Integer> heap = new PriorityQueue<>(3);
        for(int i = 0; i < arr.length; i++){
            if(heap.isEmpty() || heap.size() < 3){
                heap.offer(arr[i]);
            }else if(arr[i] > heap.peek()){
                heap.poll();
                heap.offer(arr[i]);
            }
        }
        System.out.println(heap.poll());    
    }
}

方法二 -- 快排

直接用Arrays.sort(),其内部是快排思想

import java.util.Scanner;
import static java.lang.Integer.parseInt;
import java.util.PriorityQueue;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().replace("[","").replace("]", "").split(",");
        int [] data = new int[str.length];
        for(int i = 0; i < data.length; i++){
            data[i] = parseInt(str[i]);
        }

        Arrays.sort(data);
        System.out.println(data[data.length - 3]);
    }
}