K phần tử xuất hiện nhiều nhất (Top K Frequent Elements) trong Python

Giả sử chúng ta có một mảng số nguyên không rỗng. Chúng ta phải trả về k phần tử xuất hiện nhiều nhất. Ví dụ, nếu mảng là [1,1,1,1,2,2,3,3,3] và k = 2, kết quả sẽ là [1, 3].

Để giải quyết bài toán này, chúng ta làm theo các bước sau:

• Tạo từ điển tan_suat_so để lưu tần suất mỗi số.

• Tạo từ điển danh_sach_tan_suat ánh xạ tần suất sang danh sách các số có tần suất đó.

• Duyệt qua mảng đầu vào để điền tan_suat_so.

• Duyệt qua tan_suat_so để xây dựng danh_sach_tan_suat.

• Duyệt từ tần suất cao nhất xuống thấp, thêm các phần tử vào kết quả cho đến khi đủ k phần tử.

Ví dụ

class Solution(object):
    def topKFrequent(self, nums, k):
        tan_suat_so = {}
        danh_sach_tan_suat = {}
        for i in nums:
            if i not in tan_suat_so:
                tan_suat_so[i] = 1
            else:
                tan_suat_so[i] += 1
        for khoa, gia_tri in tan_suat_so.items():
            if gia_tri not in danh_sach_tan_suat:
                danh_sach_tan_suat[gia_tri] = [khoa]
            else:
                danh_sach_tan_suat[gia_tri].append(khoa)
        ket_qua = []
        for i in range(len(nums), 0, -1):
            if i in danh_sach_tan_suat:
                ket_qua.extend(danh_sach_tan_suat[i])
            if len(ket_qua) >= k:
                break
        return ket_qua

ob1 = Solution()
print(ob1.topKFrequent([1,1,1,1,2,2,3,3,3], 2))

Đầu vào

[1,1,1,1,2,2,3,3,3] 2

Đầu ra

[1, 3]