Giả sử chúng ta có một danh sách các số được gọi là nums. Nếu tần suất của một số thường xuyên nhất trong nums là k. Chúng ta phải tìm độ dài của một danh sách con ngắn nhất sao cho tần suất xuất hiện nhiều nhất của mục đó cũng là k.
Vì vậy, nếu đầu vào là nums =[10, 20, 30, 40, 30, 10], thì đầu ra sẽ là 3, bởi vì ở đây các số thường gặp nhất là 10 và 30, ở đây k =2. Nếu chúng ta chọn danh sách phụ [30, 40, 30] đây là danh sách phụ ngắn nhất có 30 và tần suất của nó cũng là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- L:=kích thước của nums
- rnums:=đảo ngược của nums
- d:=một bản đồ chứa tần số của từng phần tử có trong nums
- mx:=tối đa trong danh sách tất cả các giá trị của d
- vs:=danh sách k cho mỗi k trong d nếu d [k] giống với mx
- mn:=L
- cho mỗi v trong vs, do
- mn:=tối thiểu của mn và ((L - (chỉ số của v tính bằng rnums) - (chỉ số của v tính bằng num))
- trả lại mn
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import Counter def solve(nums): L = len(nums) rnums = nums[::-1] d = Counter(nums) mx = max(d.values()) vs = [k for k in d if d[k] == mx] mn = L for v in vs: mn = min(mn, (L - rnums.index(v)) - nums.index(v)) return mn nums = [10, 20, 30, 40, 30, 10] print(solve(nums))
Đầu vào
[10, 20, 30, 40, 30, 10]
Đầu ra
3