题解 | #第k轻的牛牛#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param weights int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def findKthSmallest(self , weights: List[int], k: int) -> int:
        # write code here
        max_w, min_w = weights[0], weights[0]
        min_ws = [min_w]
        # 时间复杂度为O(n)，则意味着只能遍历一次数组
        # 用一个长度为k的数组来记录最小的k个体重，每找到一个按顺序插入
        for w in weights[1:]:
            if len(min_ws) < k:
            # 结果数组数量不足k个，则直接找位置插入数据
            # 大于当前最大的，则直接插入队尾
                if w >= max_w:
                    min_ws.append(w)
                # 小于当前最小的，则插入队首
                elif w <= min_w:
                    min_ws.insert(0, w)
                # 否则在队里找到第一个比当前值大的位置插入
                else:
                    for j in range(len(min_ws)):
                        if min_ws[j] > w:
                            min_ws.insert(j,w)
                            break
            else:
            # 结果数量等于k个，则每个数都要与结果数组里的值比较
            # 如果是居间的一个值，则把最大的值pop掉，然后在里边找到第一个比它大的位置插入
                if w < max_w and w > min_w:
                    min_ws.pop()
                    for j in range(len(min_ws)):
                        if min_ws[j] > w:
                            min_ws.insert(j, w)
                            break
            # 如果比最小值更小，则把队尾的值pop掉，把当前值插入队首
                elif w < min_w:
                    min_ws.pop()
                    min_ws.insert(0, w)
            # 最大值与最小值始终在结果数组的队尾和队首
            max_w = min_ws[-1]
            min_w = min_ws[0]
        
        return min_ws[-1]