【LeetCode】215. 数组中的第K个最大元素（高频！字节面试题）&变形（列表是单峰）

1. 题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

2. 思路

本题和【剑指 Offer】 40. 最小的k个数. 相似

【求最大 top k 问题用最小堆，求最小 top k 问题用最大堆】

维护一个长度为 $k$ 的小顶堆
随后从第 $k + 1$ 个数开始遍历，如果当前遍历到的数比大顶堆的堆顶的数要大，就把堆顶的数弹出，再插入当前遍历到的数。而后再 heapify 操作恢复一下最小堆结构
最后将小顶堆的堆顶（即第 $k$ 小的数）返回即可。

3. 代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        hp = nums[:k]
        heapq.heapify(hp)
        for i in range(k, n):
            if hp[0] < nums[i]:
                hp[0] = nums[i]
                heapq.heapify(hp) 
        return hp[0]

时间复杂度 ： > $O (N l o g k)$
因为在 for 循环里多了 heapify() 的操作

参考：

【剑指 Offer】 40. 最小的k个数.

====================================================
变形题是第四范式的算法一面题

变形：

给定一个规则的list, 形如山峰（满足单峰，且峰值点有可能在端点）：[1,3,9,10,8,6,2]，可能存在重复值
请写出程序，返回第k大的数，

不使用内置排序程序

解题思路 & 代码

由于有峰值的特性，最终的时间复杂度肯定得低于遍历一遍的 $O (N)$ 法，所以考虑二分法。

由二分法找到最大值（峰值）的索引
根据峰值的索引，设置两个指针，分别从峰值往两侧探索

#coding=utf-8
import sys 
#str = input()
#print(str)
import heapq
""" def findKthLargest1(nums, k): """
	小顶堆
	""" n = len(nums) hp = nums[:k] heapq.heapify(hp) for i in range(k, n): if hp[0] < nums[i]: heapq.heappop(hp) heapq.heappush(hp, nums[i]) return hp[0] """
def searchPeakIndex(nums):
    left, right = 0, len(nums) - 1
    # 特殊判断峰在端点的情况
    if nums[left] > nums[left + 1]:
        return 0
    if nums[right - 1] < nums[right]:
        return len(nums) - 1

    while left <= right:
        pivot = left + (right - left) // 2
        if nums[pivot - 1] < nums[pivot] and nums[pivot] > nums[pivot + 1]: # 刚好在峰值处
            return pivot
        if nums[pivot - 1] < nums[pivot] < nums[pivot + 1]:  # 左半部分，升序
            left = pivot + 1
        elif nums[pivot - 1] > nums[pivot] > nums[pivot + 1]: # 右半部分，升序
            right = pivot - 1
    return -1


def findKthLargest2(nums, index, k):
	""" 指针法 index: 假设已经二分法已经找到了峰值位置对应的索引 """
    i = index - 1
    j = index + 1
    n = len(nums)
    res = [index]
    while i >=0 and j <= n-1:
        if nums[i] >= nums[j]:
            res.append(i)
            res.append(j)
        i -= 1
        j += 1
    return nums[res[k-1]]

if __name__ == '__main__':
    nums = [1,3,9,10,8,6,2]
    k = 4
    #res1 = findKthLargest1(nums, k)
    #print("res1", res1)
    index = searchPeakIndex(nums)
    res2 = findKthLargest2(nums, index, k) # 示例中，峰值 10 的索引为 3
    print("res2", res2)

【LeetCode】215. 数组中的第K个最大元素（高频！字节面试题）&变形（列表是单峰）

1. 题目描述

2. 思路

3. 代码

推荐如下写法：

参考：

变形：

解题思路 & 代码