Leetcode刷题之——数组中的第K个最大元素（python解决）

题目描述：

解决方案1：找规律法

题目描述的是，要找到数组中第K大的数，即该数组中，比找到的数要大的有K-1个，如果将数组按照由大到小的降序进行排列的话，只要输出第K个数就可以直接获得想要得到的数字。

解决代码如下：

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums = sorted(nums, reverse=True)
        return nums[k-1]

提交结果：

解决方案2：堆排序

采用堆排序方法中的大顶堆方法，找到第K大的元素。由于大顶堆是一棵父结点都大于叶子结点的二叉树，所以，只要保持大顶堆的元素小于等于K，那么大顶堆就保留了前K个最大的元素了。即堆顶元素就是想要的目标元素。

代码如下：

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

提交结果：

解决方案三：快速排序：

快速排序即先选择一个元素作为数组中的中枢值pivot，找到中枢所在的位置，再递归地在pivot左右各进行快速排序。本题要找第K大的元素，即也是找第N-K小的元素，也可使用快速排序的方法，根据每个pivot的位置与N-K的大小是否一致，来判断需要往左寻找还是往右寻找。

解决代码如下：

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(left, right, pivot_index):
            pivot = nums[pivot_index]
            # 1. move pivot to end
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]  
            
            # 2. move all smaller elements to the left
            store_index = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store_index], nums[i] = nums[i], nums[store_index]
                    store_index += 1

            # 3. move pivot to its final place
            nums[right], nums[store_index] = nums[store_index], nums[right]  
            
            return store_index
        
        def select(left, right, k_smallest):
            """
            Returns the k-th smallest element of list within left..right
            """
            if left == right:       # If the list contains only one element,
                return nums[left]   # return that element
            
            # select a random pivot_index between 
            pivot_index = random.randint(left, right)     
                            
            # find the pivot position in a sorted list   
            pivot_index = partition(left, right, pivot_index)
            
            # the pivot is in its final sorted position
            if k_smallest == pivot_index:
                 return nums[k_smallest]
            # go left
            elif k_smallest < pivot_index:
                return select(left, pivot_index - 1, k_smallest)
            # go right
            else:
                return select(pivot_index + 1, right, k_smallest)

        # kth largest is (n - k)th smallest 
        return select(0, len(nums) - 1, len(nums) - k)

提交结果：