数组中的第K个最大元素

面试高频考题—TOP K问题

选自Leetcode 数组中第K大元素

• 题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

• 算法思路：我们知道快速排序的每一次排序结果 都会确定 基准元素 的位置 假设为 mid，另外题目要求找的是第K个最大的元素，而不是第k个最小的 元素，所以我们需要找到第K个最大的元素 下标与 第k个最小的 元素 下标之间的转换关系 我们举个例子

  假设共有100个数 分别是从1到100，那么 第1个最大的数 100，也就是第100个最小的元素，这个最小元素（也就是100）在排序后 所处的下标应该是99,

  同理， 那么 第2个最大的数 99，也就是第99个最小的元素，这个最小元素（也就是99）在排序后 所处的下标应该是98

  所以 我们很容易找到类比关系 第K个最大的元素 下标与 第k个最小的 元素 下标之间的转换关系为

  第k个最小的 元素 下标 = 数组长度 - 第K个最大的元素 下标

• 我们在得到基准元素 的位置 mid后，就可以 通过比较 mid 与 k 之间的关系 来判断我们所要找的数 在mid之前 还是之后

  算法描述到这里 已经呼之欲出了，下面给出python 版本的 答案

  class Solution:
      def findKthLargest(self, nums: List[int], k: int) -> int:
          # TOP K问题
          # 使用快速排序的思想
          def quick_sort(nums,low,high):
              flag=nums[low]
              while low<high: # 这里没有等于号
                  #从右到左 找比flag小的数
                  while low<high and nums[high]>=flag:#????
                      high-=1
                  nums[low]=nums[high]
                  # 从左到右 找flag 大的数
                  while low<high and nums[low]<=flag:
                      low+=1
                  nums[high]=nums[low]
              nums[low]=flag
              return low
          
          low=0
          random.shuffle(nums) #YYDS
          high=len(nums)-1
          k=len(nums)-k 
          while low<=high:
              mid=quick_sort(nums,low,high)
              if mid==k:
                  return nums[mid]
              elif mid>k:
                  high=mid-1
              else:
                  low=mid+1