Giả sử chúng ta có một mảng các số nguyên không rỗng. chúng ta phải trả về k phần tử thường xuyên nhất. Vì vậy, nếu các phần tử là [1,1,1,1,2,2,3,3,3] và k =2, thì kết quả sẽ là
Về mặt chính thức, hàm nên -
- Trả về true nếu tồn tại i, j, k
- sao cho arr [i]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- num_freq =một bản đồ trống, freq_list:=một bản đồ trống
- cho mỗi phần tử i trong nums
- nếu tôi không thuộc num_freq, thì num_freq [i]:=1, nếu không, hãy tăng num_freq [i] lên 1
- cho mỗi cặp khóa-giá trị trong bản đồ num_freq
- nếu giá trị không có trong freq_list, thì freq_list [value]:=một danh sách có [key], nếu không thì chèn key vào mảng freq_list [value]
- res:=danh sách trống
- for i:=độ dài của các số đến 0
- nếu tôi ở trong freq_list, thì hãy thêm các phần tử của freq_list [i] vào res
- nếu độ dài của res> =k, thì ngắt
- trả về kết quả
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object):
def topKFrequent(self, nums, k):
number_frequency = {}
frequency_list ={}
for i in nums:
if i not in number_frequency:
number_frequency[i] = 1
else:
number_frequency[i] += 1
for key,value in number_frequency.items():
if value not in frequency_list:
frequency_list[value] = [key]
else:
frequency_list[value].append(key)
result = []
for i in range(len(nums),0,-1):
if i in frequency_list:
result.extend(frequency_list[i])
if len(result) >=k:
break
return result
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]