LeetCode 215. 数组中的第K个最大元素——Python实现（堆排序、快速排序）_数组中的第k个最大元素 leetcode python

1、用堆排序的方法

# -*- coding: utf-8 -*-
"""
@File  : heap_find_kth_largest.py
@Author: zhang_san
@Time  : 2020/8/28 19:54
@des   : 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
         即：在数组进行降序排列之后，取 第 k 个位置上的值。这里不考虑重复的情况，比如排序后为[6, 5, 5, 4, 3, 2, 1]，这里
         的第 4 个最大的元素就是 4。
         所以这种情况，用排序算法是最好的。最直接的方式是使用大堆排序，这样当找到第 k 个最大的值的时候就可以停止继续排序了。
"""
 
 
class Solution:
    def findKthLargest(self, nums, k: int) -> int:
        def heap_sort(nums, root, last_index):
            left = 2 * root + 1
            while left <= last_index:
                # 如果左节点刚好是最后一个节点，则只比较root和left这两个节点，并且可以停止继续向下比较了
                if left == last_index:
                    if nums[left] > nums[root]:
                        nums[left], nums[root] = nums[root], nums[left]
                    break
 
                # 如果当前root节点的子节点不是最后一个节点，则获取其子节点里更大的那个节点，然后跟root节点的值对比
                if nums[left + 1] > nums[left]:   # 如果右子节点比左子节点大，那么交换右子节点
                    left += 1
 
                # 对比root节点和子节点中比较大的节点，如果当前节点比其左右子节点都大，那么不需要再继续向下进行比较了，可以跳出了
                if nums[root] < nums[left]:
                    nums[root], nums[left] = nums[left], nums[root]
                    root = left
                    left = 2 * root + 1
                else:
                    break
 
        # 创建一个大根堆，大根堆得每颗子树也是大根堆，所以，从最后一个有子节点的非叶子节点开始，往前遍历，形成大根堆
        for i in range(int((len(nums)-1)/2), -1, -1):
            heap_sort(nums, i, len(nums) - 1)
 
        # 在大根堆的基础上交换第一个节点个最后一个节点
        for last_index in range(len(nums) - 1, -1, -1):
            nums[0], nums[last_index] = nums[last_index], nums[0]
            k -= 1
            if k == 0:
                return nums[last_index]
            heap_sort(nums, 0, last_index - 1)
 
 
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
s = Solution()
print(s.findKthLargest(nums, 1))

2、用快速排序的方法

# -*- coding: utf-8 -*-
"""
@File  : quick_find_kth_largest.py
@Author: zhang_san
@Time  : 2020/8/30 15:59
@des   : 用快速排序的思想。
"""
import random
 
 
class Solution:
    def findKthLargest(self, nums, k: int) -> int:
        def partition(nums, left, right):
            # 选择一个pivot点
            p = random.randint(left, right)
            nums[p], nums[left] = nums[left], nums[p]
            p = left
 
            # 进行快速排序, left始终指向的是最后一个小于pivot数的位置，所以最后要进行交换
            while left < right:
                if nums[right] < nums[p]:
                    left += 1
                    nums[left], nums[right] = nums[right], nums[left]
                else:
                    right -= 1
            nums[p], nums[left] = nums[left], nums[p]
            return left
 
        target = len(nums) - k
        left, right = 0, len(nums) - 1
 
        while True:
            pivot = partition(nums, left, right)
 
            # 如果找到了就直接返回相应位置的值
            if pivot == target:
                return nums[target]
 
            # 如果没找到，则比较当前pivot与target的大小，缩小搜索的范围，并继续寻找合适的pivot
            if target < pivot:
                right = pivot - 1
            else:
                left = pivot + 1
 
 
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
s = Solution()
print(s.findKthLargest(nums, 4))