Python口试宝典第30题：找出第K大元素

标题

        给定一个整数数组nums，请找出数组中第K大的数，包管答案存在。此中，1 <= K <= nums数组长度。
        示例 1：

2. 输入：nums = [3, 2, 1, 5, 6, 4], K = 2
3. 输出：5

复制代码

        示例 2：

2. 输入：nums = [50, 23, 66, 18, 72], K = 3
3. 输出：50

复制代码

快速选择算法

        快速选择算法的根本头脑是：通过一次分别利用，将数组分为两部分，使得一部分的全部元素都小于另一部分的全部元素；假如K恰好位于分别点，则我们找到了答案；否则，我们只必要在较小的那一部分中继承探求。使用快速选择算法求解本题的告急步调如下。
        1、选取一个基准元素pivot。
        2、对数组举行分别，使得全部小于pivot的元素都在其左侧，全部大于pivot的元素都在其右侧。
        3、根据pivot的位置，决定下一步的利用。
        （1）假如pivot的位置恰好是K-1，那么pivot就是我们要找的第K大的元素。
        （2）假如pivot的位置大于K-1，那么我们必要在左侧子数组中继承查找。
        （3）假如pivot的位置小于K-1，那么我们必要在右侧子数组中继承查找。
        4、重复上述步调，直到找到终极答案。
        根据上面的算法步调，我们可以得出下面的示例代码。

2. def partition(nums, left, right):
3.     # 选择最右边的元素作为基准
4.     pivot = nums[right]
5.     i = left
6.     for j in range(left, right):
7.         if nums[j] < pivot:
8.             nums[i], nums[j] = nums[j], nums[i]
9.             i += 1
10.     nums[i], nums[right] = nums[right], nums[i]
11.     return i
13. def quickselect(nums, left, right, k):
14.     if left == right:
15.         return nums[left]
17.     pivot_index = partition(nums, left, right)
18.     # 判断基准的位置
19.     if k == pivot_index + 1:
20.         return nums[k - 1]
21.     elif k < pivot_index + 1:
22.         return quickselect(nums, left, pivot_index - 1, k)
23.     else:
24.         return quickselect(nums, pivot_index + 1, right, k)
25.   
26. def find_Kth_largest_element_by_quick_select(nums, k):
27.     # 因为数组索引从0开始，而题目要求的是第k大的数，所以需要转换为第n-k+1小的数  
28.     n = len(nums)
29.     return quickselect(nums, 0, n - 1, n - k + 1)
30.   
31. nums = [3, 2, 1, 5, 6, 4]
32. k = 2
33. print(find_Kth_largest_element_by_quick_select(nums, k))
35. nums = [50, 23, 66, 18, 72]
36. k = 3
37. print(find_Kth_largest_element_by_quick_select(nums, k))

复制代码

堆排序法

        堆排序法的根本头脑是：使用最小堆的性子来维护一个巨细为K的堆，如许我们就可以在遍历数组的过程中不停更新这个堆，终极堆顶的元素就是我们要找的第K大的数。使用堆排序法求解本题的告急步调如下。
        根据上面的算法步调，我们可以得出下面的示例代码。
        1、导入heapq模块，使用它提供的heappush和heappop函数来利用堆。
        2、创建一个巨细为K的空堆。
        3、遍历数组nums，对于每个元素x，举行以下利用。
        （1）假如堆的巨细小于K，则直接将x插入堆中。
        （2）假如堆的巨细便是K且x大于堆顶元素，则弹出堆顶元素，并将x插入堆中。
        4、终极，堆顶元素即为第K大的元素。

2. import heapq
4. def find_Kth_largest_element_by_min_heap(nums, k):
5.     # 创建一个大小为k的最小堆
6.     min_heap = []
7.    
8.     # 遍历数组中的每一个元素
9.     for num in nums:
10.         # 如果堆的大小小于k，则直接插入
11.         if len(min_heap) < k:
12.             heapq.heappush(min_heap, num)
13.         # 如果堆已满并且当前元素比堆顶元素大，则替换堆顶元素
14.         elif num > min_heap[0]:
15.             heapq.heapreplace(min_heap, num)
16.    
17.     # 堆顶元素即为第k大的元素
18.     return min_heap[0]
20. nums = [3, 2, 1, 5, 6, 4]
21. k = 2
22. print(find_Kth_largest_element_by_min_heap(nums, k))
24. nums = [50, 23, 66, 18, 72]
25. k = 3
26. print(find_Kth_largest_element_by_min_heap(nums, k))

复制代码

总结

        快速选择算法的时间复杂度均匀情况下为O(n)，最坏情况下（每次选择的基准都是最小或最大值时）为O(n^2)。由于最坏情况下的性能较差，一样平常必要随机化选择基准来制止最坏情况的发生。堆排序法的时间复杂度为O(n*logK)，这是由于每次插入和删除利用的时间复杂度为O(logK)，统共有n次利用。
        总的来说，快速选择算法实用于大多数情况，特别是在K靠近数组长度一半时。它不必要额外的存储空间（除了递归栈），而且通常情况下性能很好。堆排序法更恰当于K相对于数组长度较小的情况，由于随着K的增长，性能会渐渐变差。别的，它必要额外的存储空间来维护堆。