Chương trình tìm độ dài dãy con ngắn nhất chứa phần tử xuất hiện nhiều nhất Python

Cho mảng nums. Nếu tần suất lớn nhất của phần tử là k. Tìm độ dài dãy con ngắn nhất mà tần suất lớn nhất trong dãy con đó cũng bằng k.

Ví dụ: nums=[10,20,30,40,30,10] → 3 (tần suất max=2 cho 10 và 30; dãy con [30,40,30] độ dài 3 có tần suất 30 là 2).

Giải thuật (Vị trí đầu/cuối của phần tử tối đa)

1. Đếm tần suất, tìm mx = tần suất lớn nhất
2. Tìm các phần tử có tần suất = mx
3. Với mỗi phần tử đó: độ dài dãy con ngắn nhất chứa tất cả nó = last_index - first_index + 1
4. Lấy min của các độ dài đó

Ví dụ triển khai

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:
        first = nums.index(v)
        last = L - 1 - rnums.index(v)
        mn = min(mn, last - first + 1)
    return mn

print(solve([10, 20, 30, 40, 30, 10]))

Đầu vào

[10, 20, 30, 40, 30, 10]

Đầu ra

3