题解 | #第k轻的牛牛#

• 题目考察的知识点 : 快排，快速选择算法
• 题目解答方法的文字分析：

1. 首先，在 left 和 right 区间内随机选取一个元素作为 pivot，并将其与 right 位置上的元素互换。然后使用 i 指针从 left 开始向右扫描，使用 j 指针从 right - 1 开始向左扫描。在扫描的过程中，如果发现 i 指针指向的元素大于 pivot，或者 j 指针指向的元素小于等于 pivot，就交换它们的位置。最终，将 pivot 放在 i 指针所指的位置上，并返回 i 指针的位置。然后根据 i 与 k 的大小关系，递归地对左侧或右侧区间进行快速选择，直到找到下标为 k 的元素为止。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param weights int整型一维数组
# @param k int整型
# @return int整型
#
import random


class Solution:
    def findKthSmallest(self, weights: List[int], k: int) -> int:
        return self.quickSelect(weights, 0, len(weights) - 1, k - 1)

    def quickSelect(self, weights: List[int], left: int, right: int, k: int) -> int:
        if left == right:
            return weights[left]

        pivot_index = random.randint(left, right)
        pivot = weights[pivot_index]
        weights[pivot_index], weights[right] = weights[right], weights[pivot_index]

        i, j = left, right

        while i < j:
            while i < j and weights[i] <= pivot:
                i += 1
            weights[j] = weights[i]
            while i < j and weights[j] >= pivot:
                j -= 1
            weights[i] = weights[j]

        weights[j] = pivot

        if i == k:
            return weights[i]
        elif i > k:
            return self.quickSelect(weights, left, i - 1, k)
        else:
            return self.quickSelect(weights, i + 1, right, k)