หาค่าที่เป็นอันดับ k จากมากไปน้อยในอาร์เรย์ unsorted
ตัวอย่าง
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
หลายวิธีแก้
| วิธี | Time | Space | หมายเหตุ |
|---|---|---|---|
| Sort แล้ว取 index | O(n log n) | O(1) หรือ O(n) | ง่ายที่สุด |
| Min-Heap ขนาด k | O(n log k) | O(k) | เหมาะ k << n |
| QuickSelect | O(n) average | O(1) | ซับซ้อนกว่า |
โค้ดง่ายที่สุด (Sort)
class Solution:
def findKthLargest(self, nums, k):
nums.sort(reverse=True)
return nums[k-1]
# ทดสอบ
sol = Solution()
print(sol.findKthLargest([56,14,7,98,32,12,11,50,45,78,7,5,69], 5)) # 50
โค้ด Heap (แนะนำสำหรับ k เล็ก)
import heapq
class Solution:
def findKthLargest(self, nums, k):
return heapq.nlargest(k, nums)[-1]
# หรือ manual heap
def findKthLargest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for n in nums[k:]:
if n > heap[0]:
heapq.heapreplace(heap, n)
return heap[0]
สรุป
ใช้ heapq.nlargest หรือ sort ตรงไปตรงมา QuickSelect ใช้เมื่อต้องการ O(n) worst-case guarantee
