Top K Frequent Elements
Bạn nhận được một mảng số nguyên nums và một số nguyên k. Hãy trả về k giá trị xuất hiện thường xuyên nhất trong nums, theo thứ tự từ thường xuyên nhất đến ít thường xuyên hơn. Nếu hai giá trị xuất hiện cùng số lần, giá trị nhỏ hơn đứng trước.
Mỗi giá trị chỉ xuất hiện một lần trong câu trả lời, dù nó xuất hiện bao nhiêu lần trong nums, và k không bao giờ lớn hơn số lượng giá trị khác nhau.
Hàm
- numsinteger-array
- các giá trị cần đếm
- kinteger
- cần trả về bao nhiêu giá trị
- Trả vềinteger-array
- k giá trị xuất hiện thường xuyên nhất, theo thứ tự tần suất giảm dần; nếu hòa, giá trị nhỏ hơn đứng trước
Ràng buộc
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, vàkkhông lớn hơn số lượng giá trị khác nhau trongnums.
Ví dụ
- Đầu vào
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Đầu ra
- [4, 1]
- Giải thích
4xuất hiện bốn lần,1xuất hiện ba lần, còn2và3mỗi số xuất hiện một lần. Hai giá trị xuất hiện nhiều nhất là4, sau đó là1.
- Đầu vào
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Đầu ra
- [-2, 5]
- Giải thích
-2,5và7đều xuất hiện hai lần, còn9xuất hiện một lần. Ba giá trị cùng đứng đầu, nên hai giá trị nhỏ hơn là-2và5chính là đáp án.
- Đầu vào
- nums = [8]k = 1
- Đầu ra
- [8]
- Giải thích
- Chỉ có một giá trị, nên đây là giá trị xuất hiện nhiều nhất.
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Trước tiên, hãy tìm hiểu tần suất xuất hiện của từng giá trị. Cấu trúc dữ liệu nào ánh xạ mỗi giá trị với số lần xuất hiện của nó chỉ trong một lượt?
Khi đã có số lần xuất hiện, bạn muốn tìm
kgiá trị tốt nhất theo một thứ tự: giá trị có số lần xuất hiện cao hơn đứng trước, nếu bằng nhau thì giá trị nhỏ hơn đứng trước. Sắp xếp mọi giá trị riêng biệt cũng được. Min-heap có kích thướckchỉ giữ lại những giá trị vẫn có thể nằm trong đáp án.Một số đếm là số nguyên từ 1 đến
n. Tạo một nhóm cho mỗi số đếm, nhómcchứa các giá trị xuất hiện đúngclần, rồi đọc các nhóm từ số đếm cao nhất xuống thấp nhất. Điền các nhóm bằng cách duyệt các giá trị từ nhỏ nhất đến lớn nhất, khi đó mỗi nhóm đã được sắp xếp theo thứ tự khi hòa.
Lời giải
Chỉ cần một lượt duyệt với bảng băm (hash map) để đếm mọi giá trị. Sau đó, chọn k giá trị tốt nhất: sắp xếp tất cả d giá trị riêng biệt tốn O(d log d), dùng đống tối thiểu có kích thước k tốn O(d log k), còn vì số lần xuất hiện nằm trong khoảng từ 1 đến n, sắp xếp theo bucket (bucket sort) sẽ sắp xếp các giá trị theo số lần xuất hiện mà không cần so sánh.
Đếm, rồi sắp xếp theo số lượng
Ý tưởng
Đếm bằng bảng băm (hash map): [4, 1, 4, 2, 1, 4, 3, 1, 4] cho kết quả 4 → 4, 1 → 3, 2 → 1, 3 → 1. Sau đó sắp xếp các giá trị khác nhau theo số lần xuất hiện, từ cao xuống thấp, rồi theo giá trị, từ thấp lên cao. Thứ tự so sánh đó chính là thứ tự đáp án, nên k phần tử đầu tiên là đáp án.
Sắp xếp d giá trị khác nhau tốn O(d log d), tương đương khoảng 1.3 × 10^5 phép so sánh với 10^4 giá trị khác nhau. Cách này sắp xếp mọi giá trị, trong khi chỉ cần quan tâm đến k giá trị đầu tiên.
Thuật toán
- Đếm từng giá trị trong một bản đồ băm.
- Đưa các giá trị riêng biệt vào một danh sách.
- Sắp xếp danh sách theo số lần xuất hiện từ cao đến thấp, và theo giá trị từ thấp đến cao khi số lần xuất hiện bằng nhau.
- Trả về
kgiá trị đầu tiên.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Giữ k phần tử tốt nhất trong min-heap
Ý tưởng
Chỉ giữ lại k ứng viên. Chỉ giữ giá trị mới nếu nó tốt hơn ứng viên yếu nhất, trong đó yếu hơn nghĩa là có số lần xuất hiện thấp hơn, hoặc có cùng số lần xuất hiện nhưng giá trị lớn hơn. Min-heap được sắp xếp theo quy tắc đó sẽ giữ ứng viên yếu nhất ở trên cùng, có thể đọc trong O(1) và thay thế trong O(log k). Có thể loại bỏ giá trị không tốt hơn giá trị trên cùng, vì đã giữ lại k giá trị tốt hơn.
Heap chỉ được sắp xếp một phần, và thao tác lấy phần tử trả về giá trị yếu nhất trước, vì vậy hãy ghi đáp án từ vị trí cuối cùng trở về đầu. Việc chọn tốn O(d log k), nhanh hơn sắp xếp khi k nhỏ hơn d rất nhiều.
Thuật toán
- Đếm số lần xuất hiện của từng giá trị trong bản đồ băm.
- Với mỗi giá trị riêng biệt, thêm giá trị đó vào khi đống còn ít hơn
kgiá trị. - Khi đống đã đầy, so sánh giá trị đó với giá trị trên cùng, tức giá trị yếu nhất đang được giữ lại. Nếu giá trị mới mạnh hơn, đưa nó lên trên cùng rồi vun đống xuống.
- Lấy giá trị khỏi đống
klần, ghi từng giá trị vào đáp án từ vị trí cuối cùng đến vị trí đầu tiên.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultĐếm, rồi sắp xếp theo nhóm dựa trên số lượng
Ý tưởng
Số lần xuất hiện là một số nguyên dương từ 1 đến n, vì vậy hãy đưa mỗi giá trị vào nhóm tương ứng với số lần xuất hiện của nó rồi đọc các nhóm từ n trở xuống. Các giá trị sẽ xuất hiện theo thứ tự tần suất giảm dần và không bao giờ cần so sánh hai số lần xuất hiện với nhau.
Để xử lý trường hợp bằng nhau, hãy đếm bằng một mảng gồm R = 2 × 10^4 + 1 bộ đếm, đặt giá trị v tại chỉ số v + 10^4, rồi duyệt từ giá trị nhỏ nhất trở lên và thêm từng giá trị vào nhóm tương ứng. Như vậy, mỗi nhóm sẽ được điền theo thứ tự tăng dần, chính là thứ tự dùng để xử lý các giá trị bằng nhau. Trong ví dụ thứ hai, khi duyệt, ta đưa -2, 5, 7 vào nhóm 2, rồi k = 2 chọn -2 và 5.
Độ phức tạp tổng thể là O(n + R). Nếu dùng bảng băm thay cho mảng, các nhóm sẽ được điền theo thứ tự của bảng và cần sắp xếp từng nhóm.
Thuật toán
- Đếm từng giá trị trong mảng, dùng
value + 10^4làm chỉ số. - Tạo các nhóm từ 1 đến
n, mỗi nhóm là một danh sách ứng với một số lần xuất hiện có thể có. - Duyệt mảng đếm từ giá trị nhỏ nhất đến lớn nhất, rồi thêm mỗi giá trị xuất hiện vào nhóm tương ứng với số lần xuất hiện của nó.
- Đọc các nhóm từ số lần xuất hiện
ngiảm dần đến 1, lấy các giá trị cho đến khi cókgiá trị.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Lỗi thường gặp và trường hợp biên
- Phá vỡ quy tắc khi có trường hợp hòa bằng cách chọn lần xuất hiện đầu tiên hoặc thứ tự của từ điển băm. Trong ví dụ thứ hai,
-2,5và7đều xuất hiện hai lần, và chỉ quy tắc chọn giá trị nhỏ hơn mới cho kết quả[-2, 5]. - Trả về mảng của đống như hiện tại. Phần tử trên cùng là giá trị yếu nhất, tức giá trị cần xếp cuối cùng.
- Đảo ngược quy tắc xử lý trường hợp hòa của đống. Đống min trên
(count, value)loại bỏ giá trị nhỏ hơn khi số lần xuất hiện bằng nhau; hãy dùng(count, -value). - Chỉ tạo số lượng nhóm bằng số giá trị riêng biệt. Trong
[3, 3, 3, 3], một giá trị xuất hiệnnlần, nên nhómnphải tồn tại. - Trong Java, so sánh hai số đếm
Integerbằng!=. Cách này so sánh tham chiếu và gây lỗi khi số đếm vượt quá 127.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Top K Frequent Elements là bao nhiêu?
Việc đếm cần O(n). Sau đó, chọn k giá trị lớn nhất cần O(d log d) nếu sắp xếp d giá trị phân biệt, O(d log k) nếu dùng đống tối thiểu có kích thước k, hoặc một lượt duyệt các số đếm bằng sắp xếp theo nhóm. Vì d có thể đạt tới n, trong trường hợp xấu nhất, sắp xếp cần O(n log n), còn sắp xếp theo nhóm có độ phức tạp tuyến tính.
Có thể giải bài toán Top K Frequent Elements trong thời gian O(n) không?
Đúng vậy, với sắp xếp theo nhóm, vì số lần xuất hiện là số nguyên từ 1 đến n. Quickselect trên các số lần xuất hiện cũng có độ phức tạp O(n) trung bình, nhưng trường hợp xấu nhất có độ phức tạp bậc hai.
Tại sao dùng min-heap thay vì max-heap?
Một max-heap chứa tất cả các giá trị d cũng dùng được: tạo heap trong O(d) rồi lấy phần tử ra k lần, tổng cộng là O(d + k log d). Min-heap có kích thước k chỉ giữ k phần tử và phù hợp với các giá trị đến lần lượt từng phần tử, vì phần tử ở đỉnh là ứng viên cần loại bỏ.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def topKFrequent(nums, k):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Đầu ra mong đợi
[4, 1]