LeetCode 215. 数组中的第K个最大元素

116 阅读 0 评论 77 点赞

我是靠谱客的博主高贵短靴，这篇文章主要介绍LeetCode 215. 数组中的第K个最大元素，现在分享给大家，希望可以做个参考。

Description

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:

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

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

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1 全排序

对整个数组排序取前K个元素。时间O(nlogn)

Solution 2 部分排序

使用冒泡，冒k次泡能把前k大元素提取出来排好序。O(k*n)

Solution 3 堆排序

维护一个容量为K的小根堆(不能用大根堆)，最终得到没有排好序的K大元素。O(nlogk)

复制代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        minHeap = [float('-inf') for _ in range(k)]
        for n in nums:
            if n > minHeap[0]:
                heapq.heappop(minHeap)
                heapq.heappush(minHeap, n)
        return minHeap[0]

Solution 4 快排思想

时间O(n)。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findKthLargest(self, nums, k: int) -> int:
        def findK(left, right, k):
            mid = partition(left, right)
            print(mid)
            while mid != k:
                if mid < k:
                    mid = partition(mid+1, right)
                elif mid > k-1:
                    mid = partition(left, mid-1)
            return nums[k]

		# partition返回正确数字的index
        def partition(left, right):
            pivot = nums[left]
            while left < right:
                while left < right and nums[right] >= pivot: # >=!!!
                    right -= 1
                nums[left] = nums[right]
                while left < right and nums[left] <= pivot: # <= !!!
                    left += 1
                nums[right] = nums[left]
            nums[left] = pivot
            return left
        # 第k大元素在数组的位置为len(nums)-k
        ans = findK(0, len(nums)-1, len(nums)-k)
        return ans