题解 | #寻找第K大#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
# class Solution:
#     # def findKth(self , a: List[int], n: int, K: int) -> int:
#     #     """
#     #     method_1: 排序，之后输出
#     #     """
#     #     # write code here
#     #     if n <= 1 and len(a) <= 1:
#     #         return a[n]
#     #     a.sort(reverse=True)
#     #     print("rst: ", a)
#     #     return a[K-1]

#     def findKth(self , a: List[int], n: int, K: int) -> int:
#         """
#         method_2: 快排+二分查找
#         思路： 每次移动，找到一个标杆元素，然后将大于它的移动到左边，小于它的移动到右边，之后分别对左右两边使用相同的方法进行排序。
#         步骤： 
#         step1: 进行一次快排， 大元素在左，小元素在右， 得到的标杆j点。 在此之前使用随机数获取标杆元素， 防止数据分布导致每次划分不能均衡
#         step2: 如果 j + 1 = k, 那么j点就是第K大
#         step3: 如果 j + 1 > k, 那么第k大的元素就在左半段， 更新 high = j -1 , 执行step1
#         step4: 如果 j + 1 < k, 那么 第k大的元素就在右半段， 更新low = j + 1, 执行 step1
#         """
#     def partition(self, a:List[int], low:int, high:int, k:int) -> int:
#         # 随机快排划分
#         import random
#         x = random.randint(0, 10000)
#         a[low], a[x % (high - low + 1) + low] = a[x % (high - low + 1) + low], a[low]
#         v = a[low]
#         i = low + 1
#         j = high 

#         while True:
#             # 小雨标志位
#             while j >= low + 1 and a[j] < v:
#                 j -= 1
#             # 大于标志位
#             while i <= high and a[i] > v:
#                 i += 1
#             if i > j:
#                 break
#             a[i], a[j] = a[j], a[i]
#             i+= 1
#             j -= 1

#             a[low], a[j] = a[j], a[low]

#             if j +1 == k:
#                 return a[j]
#             elif j +1 < k: 
#                 return self.partition(a, j+1, high, k)
#             else:
#                 return self.partition(a, low, j-1, k)
            
#     def findKth(self, a: List[int], n:int, K:int) -> int:
#         return self.partition(a, 0, n-1, K)
import random

class Solution:
    def partition(self, a: List[int], low: int, high: int, k: int) -> int:
        #随机快排划分
        x = random.randint(0, 10000)
        a[low], a[x % (high - low + 1) + low] = a[x % (high - low + 1) + low], a[low]
        v = a[low]
        i = low + 1
        j = high
        while True:
            #小于标杆的在右
            while j >= low + 1 and a[j] < v:
                j -= 1
            #大于标杆的在左
            while i <= high and a[i] > v:
                i += 1
            if i > j:
                break
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
        a[low], a[j] = a[j], a[low]
        #从0开始，所以为第j+1大
        if j + 1 == k:
            return a[j]
        #继续划分
        elif j + 1 < k:
            return self.partition(a, j + 1, high, k)
        else:
            return self.partition(a, low, j - 1, k)
    def findKth(self , a: List[int], n: int, K: int) -> int:
        return self.partition(a, 0, n - 1, K)
		
		一涉及到这种需要动脑子的东西，就挂机。要脸，也要练