Top K numbers pattern is very useful to solve the problems that ask us to find the top / smallest / frequent K elements among a given set.
If the problem asking us to find the top / smallest / frequent K elements among a given set, we need to think about Top K numbers pattern.
LeetCode 215 - Kth Largest Element in an Array [medium]
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
You must solve it in O(n) time complexity.
We can use Heap data structure to keep track of K elements.
Solution 1:
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums = [-elem for elem in nums]
heapq.heapify(nums)
for i in range(k - 1):
heapq.heappop(nums)
return - heapq.heappop(nums)
Time Complexity: O(N log K). Space Complexity: O(K)
Solution 2:
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]
Time Complexity: O(N log K). The Python list sort() has been using the Timsort algorithm. Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort.
Note: Both sort and sorted are used to sort the elements in a list. There are two differences :
* Sorted() is an in-built Python function while sort() is a method of the class list.
* Sorted() returns a list with its element sorted while sort() is an in-place method.sort() updates the original list.
973. K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]]
Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Solution 1:
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for x, y in points:
dist = (x)** 2 + (y)** 2
heap.append([dist, x, y])
result = []
heapq.heapify(heap)
for i in range(k):
dist, x, y = heapq.heappop(heap)
result.append([x, y])
return result
Solution 2:
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points.sort(key = lambda p: p[0]*p[0]+p[1]*p[1])
return points[:k]
