215. Kth Largest Element

https://leetcode.com/problems/kth-largest-element-in-an-array/

solution

https://www.geeksforgeeks.org/kth-smallest-largest-element-in-unsorted-array/

直接法

# 不满足O(n)题目要求
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

时间复杂度：O(nlogn)
空间复杂度：O(1)

heap/ priority queue
- 寻找第k大的, 也就是堆里要保留前k大, 把较小的pop出去, 因此用小顶堆, python支持小顶堆.
- 寻找第k小的, 就要用大顶堆, python取负数

# 大顶堆和小顶堆都能实现, 但复杂度不一样，nlogn 或 nlogk

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)

            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

时间复杂度：O(nlog(k))
空间复杂度：O(k)

quick sort/ quick select
- Quick Select 的时间复杂度会退化为 O(n^2), 优化方法: 随机pivot, 三数取中法（Median of Medians）

def partition(nums, l, r, pivot_index):
    # build-in change the nums, and return the position
    # l含义: 第一个比pivot大的位置
    pivot = nums[pivot_index]
    nums[pivot_index], nums[r] = nums[r], nums[pivot_index]
    i = l
    for j in range(l, r):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[r] = nums[r], nums[i]
    return i

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l = 0
        r = len(nums) - 1
        return self.quick_select(nums, l, r, k)

    def quick_select(self, nums, l, r, k):
        while True:  # 如果只有一个元素, 确实不符合 l < r
            pivot_index = random.randint(l, r)
            pos = partition(nums, l, r, pivot_index)
            if pos == len(nums) - k:
                return nums[pos]
            elif pos > len(nums) - k:
                r = pos - 1
            else:
                l = pos + 1

    def quick_select2(self, nums, l, r, k):
        # 分治
        p = partition(nums, l, r, r)

        if p == k - 1:
          return nums[p]

        if p > k - 1:  # search lower part
          return self.quick_select2(nums, k, l, p - 1)

        # search higher part
        return self.quick_select2(nums, k, p + 1, r)

时间复杂度：O(n) -> O(n^2)
空间复杂度：O(1)

binary search

def get_count(v, nums):
    count = 0
    for num in nums:
        if num <= v:
            count += 1
    return count

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        low = min(nums)
        high = max(nums)
        while low < high:
            mid = low + (high - low) // 2
            if get_count(mid, nums) <= len(nums) - k:
                low = mid + 1
            else:
                high = mid
        return low

    def findKthSmallest(self, nums: List[int], k: int) -> int:
        low = min(nums)
        high = max(nums)
        while low < high:
            mid = low + (high - low) // 2
            if get_count(mid, nums) < k:
                low = mid + 1
            else:
                high = mid
        return low

时间复杂度：O()
空间复杂度：O()

bucket sort

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        count = {}
        for i in reversed(range(min(nums), max(nums)+1)):
            count[i] = 0
        for num in nums:
            count[num] += 1

        for val, f in count.items():
            if k > f:
                k-=f
                continue
            else:
                return val

follow up

373. Find K Pairs with Smallest Sums

超时: 注意已排序

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []

        for num1 in nums1:
            for num2 in nums2:
                heapq.heappush(heap, (-num1-num2, num1, num2))
                if len(heap) > k:
                    heapq.heappop(heap)

        res = []
        for i in heap:
            res.append([i[1], i[2]])
        return res

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []

        for i, num1 in enumerate(nums1):
            heapq.heappush(heap, [num1+nums2[0], i, 0])

        res = []
        while heap and len(res) < k:
            sum, i, j = heapq.heappop(heap)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, [nums1[i] + nums2[j + 1], i, j + 1])
        return res