【Leetcode】215—Kth Largest Elemen

一、题目描述

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

示例：

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

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

二、代码实现

1. 快速排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        import random
        random.shuffle(nums)
        self.quick_sort(nums, 0, len(nums)-1)
        return nums[-k]
    
    def quick_sort(self, nums, low, high):
        if low >= high: return
        pivot_index = self.partition(nums, low, high)
        self.quick_sort(nums, low, pivot_index-1)
        self.quick_sort(nums, pivot_index+1, high)
    
    def partition(self, nums, low, high):
        pivot = nums[low]
        while low < high:
            while low < high and pivot <= nums[high]:
                high = high - 1
            nums[low] = nums[high]
            while low < high and pivot >= nums[low]:
                low = low + 1
            nums[high] = nums[low]
        nums[low] = pivot
        return low 

注意：使用快排的时候需要打算数组，否则会导致最差时间复杂度O(n^2)。

2. 内置排序sort

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        return nums[-k]

3. 归并排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def merge_sort(arr, low, high):
            if low >= high: return
            mid = (low + high) // 2
            merge_sort(arr, low, mid)
            merge_sort(arr, mid+1, high)
            merge(arr, low, mid, high)
        
        def merge(arr, low, mid, high):
            container = []
            i, j = low, mid + 1
            while i<=mid and j<=high:
                if arr[i] <= arr[j]:
                    container.append(arr[i])
                    i = i + 1
                else:
                    container.append(arr[j])
                    j = j + 1
            if i<=mid:
                container.extend(arr[i:mid+1])
            elif j<=high:
                container.extend(arr[j:high+1])
            arr[low:high+1] = container
            return arr
        
        merge_sort(nums, 0, len(nums)-1)
        return nums[-k]

4. 堆排序

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def heapify(arr, n, i):
            largest = i
            l = 2 * i + 1
            r = 2 * i +2
            
            if l < n and arr[i] < arr[l]:
                largest = l
            
            if r < n and arr[largest] < arr[r]:
                largest = r
            
            if largest != i:
                arr[i], arr[largest] = arr[largest], arr[i] #exchange
                
                heapify(arr, n, largest)
        
        def heapSort(arr):
            n = len(arr)
            
            # Build a maxheap
            for i in range(n, -1, -1):
                heapify(arr, n, i)
            
            # exchange the max to the end
            for i in range(n-1, 0, -1):
                arr[i], arr[0] = arr[0], arr[i]
                heapify(arr, i, 0)
        
        heapSort(nums)
        return nums[-k]