leetcode215-- Kth Largest Element in an Array (重要)

leetcode215-- Kth Largest Element in an Array (重要)

题目

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

题目其实很容易懂,就是找到一个数组中的第k大的数字,当然简单的排序然后找到第len(nums)-k这个也是可以的。

但是其实是可以用快排的,因为快排的每一步都会把枢纽元的最终位置给找好,那么如果最终位置刚好就是len(nums)-k的话,不就直接可以了吗,(我是按从小到大排的,所以是len(nums)-k.) 即使不是,也可以或者考虑左边或者考虑右边,

如下

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        # method1.
        #nums.sort()
        #return nums[len(nums)-k]
        
        
        def quickSort(nums, left, right):
            i = left
            j = right
            pivot = nums[i]
            
            while i<j:
                while i<j and nums[j]>= pivot:
                    j -= 1                
                if i<j:
                    nums[i] = nums[j]
                    i += 1
                
                while i<j and nums[i]<= pivot:
                    i += 1
                if i<j:
                    nums[j] = nums[i]
                    j -= 1
                    
            nums[i] = pivot
            
            if i== len(nums)-k:
                return nums[i]
            
            elif i>len(nums)-k:
                return quickSort(nums, left, i-1)
            else:
                return quickSort(nums, i+1, right)
            
        return quickSort(nums, 0, len(nums)-1)
            

还有一点要注意,这里的第k大是记了重数的。如果不记重数的话可能要先取一个set.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦