Đề bài
Cho một mảng số nguyên nums và một số nguyên k, trả về k phần tử xuất hiện nhiều nhất trong mảng. Bạn có thể trả về các phần tử này theo bất kỳ thứ tự nào.
Ví dụ 1:
Đầu vào: nums = [1,1,1,2,2,3], k = 2
Đầu ra: [1,2]
Ví dụ 2:
Đầu vào: nums = [1], k = 1
Đầu ra: [1]
Ràng buộc:
1 <= nums.length <= 100,000
-10,000 <= nums[i] <= 10,000
k nằm trong khoảng [1, số lượng phần tử duy nhất trong mảng].
Đáp án chắc chắn là duy nhất.
Yêu cầu bổ sung: Độ phức tạp của thuật toán phải tốt hơn O(n log n), trong đó n là kích thước của mảng.
Giải pháp:
Một cách tiếp cận hiệu quả là sử dụng unordered_map để đếm tần số xuất hiện của các phần tử và sử dụng cấu trúc heap để tìm k phần tử xuất hiện nhiều nhất.
Cách làm
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
void topKFrequent(int nums[], int n, int k, int ketqua[]) {
unordered_map<int, int> tanSo;
// Đếm tần số xuất hiện của từng phần tử
for (int i = 0; i < n; i++) {
tanSo[nums[i]]++;
}
// Sử dụng heap (priority queue) để giữ k phần tử có tần số lớn nhất
priority_queue<pair<int, int>> pq;
for (auto &it : tanSo) {
pq.push({it.second, it.first});
}
// Lấy k phần tử có tần số lớn nhất
for (int i = 0; i < k; i++) {
ketqua[i] = pq.top().second;
pq.pop();
}
}
int main() {
int nums[] = {1, 1, 1, 2, 2, 3};
int n = sizeof(nums) / sizeof(nums[0]);
int k = 2;
int ketqua[k];
topKFrequent(nums, n, k, ketqua);
cout << "Cac phan tu xuat hien nhieu nhat la: ";
for (int i = 0; i < k; i++) {
cout << ketqua[i] << " ";
}
cout << endl;
return 0;
}
