973. K Closest Points to Origin

Question: K Closest Points to Origin

Solution1

想法：

一個 array 需要 return k 個最大值 → Max Heap → 從 min Heap 調整，因為 python 只能做 min Heap，把所有的數字乘上 -1 heappush 到 heap 裡面就會變成 Max Heap 了

1. heappush list 裡的所有 num，但這些 num 要 * -1: n * O(logn)
2. pop k 個 element: k * O(logn)

Time Complexity: n * O(logn)

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        max_heap = list()
        heapq.heapify(max_heap)
        for num in nums:
            heapq.heappush(max_heap, -num)
        
        for i in range(k):
            res = heapq.heappop(max_heap)
        return -res

改良

因為 heapify 只需要 O(n) 的時間，所以先 for loop nums 裡的 element 讓他們全部 * -1

heqpify(nums): O(n)

pop 取第 k 個 element: k * O(logn)

Time Complexity: k * O(logn)

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        max_heap = [-num for num in nums]
        heapq.heapify(max_heap)
        
        for i in range(k):
            res = heapq.heappop(max_heap)
        return -res

Solution2 超簡單

直接用 python sort() 函式: Time sort = merge sort + insertion sort

Time Complexity: O(nlogn)

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

Solution3

因為只取 k 之後的 → partially Quick sort

原本的 Quick sort Time complexity 是 O(nlogn)，但這裡只要固定 k 的位置後，找到 k 後面的，不用排好，只要都比 k 大，就可以 return 值了，所以是 partial，

round1: n / 2

round2: n / 2 / 2

round3: n / 2 / 2 / 2

所以 Time Complexity 變成 O(n)

1. 由小到大排序的話，第 k 大就會是 len(nums) - k 的位置，因此當排序到第 k 個位置時，k 後面都是比 k 大的時候，就可以 return nums[k] 了
2. quick_sort function，假設頭的 index = l(left), 最後一個 index = r(right):

   1. pivot：拿最後一個 num 當 pivot = nums[r]

   2. pointer：需要一個 pointer 紀錄比 pivot 大的數字

   3. round1 的時候 list 全部掃過一遍，i 從 index l(left) 走到 pivot 前一位：r - 1

      1. 掃過的數字如果比 pivot 小或等於 pivot，就留在原地，i 跟 p 都 += 1
      2. 如果比 pivot 大，i 繼續走， p 停下來，直到 nums[i] 再度比 pivot 小的時候，來跟 nums[p] 做交換，p +=

      以上兩點變成程式碼會長這樣：

      for i in range(l, r):
          if nums[i] <= pivot:
              nums[i], nums[p], = nums[p], nums[i]
              p += 1
          else:
              do nothing
      

   4. 全部走完之後，p 會留在比 pivot 大的數字上，所以就把 p 位置跟 pivot 交換： nums[p], nums[r] = nums[r], nums[p]

   5. 此時檢查 p 跟 k 的相對位置

      1. p > k: k 在 pivot 的前面，因此要繼續排序 pivot 之前的 list，範圍 l & r 變成 l = l, r = p - 1: quick_sort(l, p - 1)
      2. p < k: k 在 pivot 的後面，因此要繼續排序 pivot 之後的 list，範圍 l & r 變成 l = p + 1, r = r: quick_sort(p + 1, r)
      3. p == k: k 前面的值都小於 nums[k]；後面的值都大於 nums[k]，表示 nums[k] 是第 k 大的數字: return nums[k]

Time Complexity: best: O(n), worst O(n ** 2)

所以在 leetcode 上跑出來的時間複雜度會比上面兩種方法還要慢，但是一個很得學習的 Algorithem，分享給大家！

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        k = len(nums) - k 
        def quick_sort(l, r):
            p, pivot = l, nums[r]
            for i in range(l, r):
                if nums[i] <= pivot:
                    nums[i], nums[p] = nums[p], nums[i]
                    p += 1
            nums[p], nums[r] = nums[r], nums[p]

            if p < k:
                return quick_sort(p + 1, r)
            elif p > k:
                return quick_sort(l, p - 1)
            else:
                return nums[k]
        res = quick_sort(0, len(nums) - 1)
        return res

Video Solution