145 - 215 数组中第k个最大元素

题目

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

示例 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 ≤ 数组的长度。

解答

var findKthLargest = function(nums, k) {
  nums.sort((a, b) => a - b)
  return nums[nums.length - k]
};

Runtime: 76 ms, faster than 46.68% of JavaScript online submissions for Kth Largest Element in an Array.

Memory Usage: 35.9 MB, less than 10.00% of JavaScript online submissions for Kth Largest Element in an Array.

当然这样是不行的哈哈😂

小顶堆

就维护k个数的小顶堆，最后输出堆顶即可

堆就是一个完全二叉树，小顶堆就是堆顶是最小值

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

Runtime: 64 ms, faster than 97.38% of Python3 online submissions for Kth Largest Element in an Array.

Memory Usage: 13.5 MB, less than 100.00% of Python3 online submissions for Kth Largest Element in an Array.

用数组代替小顶堆

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-python3er-fe/

插入用二分法

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        ans = [float('-inf') for i in range(k)]

        for i in nums:
            if ans[0] >= i:
                continue
            if ans[-1] <= i:
                ans = ans[1:] + [i]
                continue

            l = 0
            r = k - 1
            while l < r:
                m = (l + r) // 2
                if i <= ans[m]:
                    r = m - 1
                elif ans[m + 1] >= i:
                     l = m
                    break
                else:
                    l = m + 1
            ans = ans[1:l + 1] + [i] + ans[l + 1:]
        return ans[0]

Runtime: 588 ms, faster than 17.89% of Python3 online submissions for Kth Largest Element in an Array.

Memory Usage: 13.4 MB, less than 100.00% of Python3 online submissions for Kth Largest Element in an Array.

快速选择

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/pythongai-jin-kuai-pai-by-pyguo/

随机选一个枢轴pivot，左边的数都比他小，右边的数都比他大。

然后比较比他大的有多少个

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if k > len(nums):
            return
        index = random.randint(0, len(nums)-1)
        pivot = nums[index]
        less_part = [i for i in nums[:index]+nums[index+1:] if i < pivot]
        great_part = [i for i in nums[:index]+nums[index+1:] if i >= pivot]
        if k-1 == len(great_part):
            return pivot
        elif k-1 < len(great_part):
            return Solution.findKthLargest(self, great_part, k)
        else:
            return Solution.findKthLargest(self, less_part, k-len(great_part)-1)

Runtime: 52 ms, faster than 99.95% of Python3 online submissions for Kth Largest Element in an Array.

Memory Usage: 13.5 MB, less than 100.00% of Python3 online submissions for Kth Largest Element in an Array.

这个方法好像不是原地算法，毕竟新建了数组。。

https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60306/Python-different-solutions-with-comments-(bubble-sort-selection-sort-heap-sort-and-quick-sort).

就是遇到小的就交换一下两者

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if k > len(nums):
            return

        def partition(l, r):
            ri = random.randint(l, r)
            nums[r], nums[ri] = nums[ri], nums[r]
            for i, v in enumerate(nums[l:r+1], l):
                if v >= nums[r]:
                    nums[l], nums[i] = nums[i], nums[l]
                    l += 1
            return l-1

        l, r = 0, len(nums)-1
        while True:
            pos = partition(l, r)
            if pos < k-1:
                l = pos+1
            elif pos > k-1:
                r = pos-1
            else:
                return nums[pos]

Runtime: 76 ms, faster than 76.71% of Python3 online submissions for Kth Largest Element in an Array.

Memory Usage: 13.5 MB, less than 90.00% of Python3 online submissions for Kth Largest Element in an Array.

反而更慢了。。