题解 | #第k轻的牛牛 ,对比三种算法！#

题意：无序数组中找第k小元素，优化时间复杂度

思路：我大概想到了三种算法，各有好坏，请君评断

1.简化版桶排序，

将数组中的元素放到作为桶数组的索引，当我们完全放完的时候，遍历桶数组，当桶数组=1（标记），

拿到所有=1的数组，即一个完成的顺序。

时间复杂度 o(n)

2.最大堆+k大小维护

将数组中的元素全部放到一个k大小的堆中，进行维护，最后取堆中的最后一个元素即可

时间复杂度 o(n*logk)

3.快速选择算法

在快速排序中，算法会递归处理划分两边，但是选择排序我们只处理一边

平均时间复杂 o(n)

对比：第一种算法空间有限，只适用于数组下标遍布均匀的情况下。

第二种，复杂度略高，适用于处理动态场景，比如不仅仅是取k小，而是找一堆，

第三种，适用于找数组中k小的最佳算法，最坏情况下复杂度o2，平均on

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int findKthSmallest (int[] weights, int k) {
        // write code here
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a); //最大堆
        for (int i = 0; i < weights.length; i++) {
            if (queue.size() < k)
                queue.offer(weights[i]);
            else {
                if (weights[i] < queue.peek()) { //当元素小的才会推
                    queue.poll();
                    queue.offer(weights[i]);
                }
            }
        }
        return queue.peek();
    }
}