题解 | #寻找第K大#

简直了，我不适合快速排序，我喜欢优先级队列 o(╥﹏╥)o

1、快速排序

• 1、先找到一个中轴位置（比如第一个），从中轴位置后一个开始循环
• 2、从左往右，直到找到一个比中轴位置元素大的数，记住它的位置i，此时它左边都是比中轴元素小的数
• 3、从右往左，直到找到一个比中轴元素小的数，记住它的位置j，此时它右边都是比中轴元素大的数
• 4、只要i的位置在j之前，交换i和j，使得当前i和i的左边都是比中轴元素小的数，j和j的右边都是比中轴元素大的数
• 5、重复2-4
• 6、跳出循环时，i的位置或等于j或大于j，且i及i的左边都比中轴元素小，j及j的右边都比中轴元素大，但是由于i的位置可能会大于j，所以交换j和中轴元素

import java.util.*;

public class Solution {
        public int findKth(int[] a, int n, int K) {
           int[] mid = quickSort(a,  0, a.length - 1);
        
            return mid[a.length-K];
    }

    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //获取中轴元素所处的位置
            int mid = partition(arr, left, right);
            //进行分割
            arr = quickSort(arr, left, mid - 1);
            arr = quickSort(arr, mid + 1, right);
        }
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        //选取中轴元素
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            // 向右找到第一个小于等于 pivot 的元素位置
            while (i <= j && arr[i] <= pivot) i++;
            // 向左找到第一个大于等于 pivot 的元素位置
            while(i <= j && arr[j] >= pivot ) j--;
            if(i >= j)
                break;
            //交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        // 使中轴元素处于有序的位置
        arr[j] = pivot;
        return j;
    }

}

2、优先级队列

• 优先级队列实现了Comparator接口，默认对自然数进行有序排序，最小的在队首

int[] a = {1,3,5,78,4,2,64,2,6,4,3,7,3,4};
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int k = 8;
        for(Integer n:a){
            if(queue.size()<=k){
                queue.add(n);
            }else{
                if(queue.peek()<n){
                    queue.poll();
                    queue.add(n);
                }
            }
        }
        System.out.println(queue.peek());