Cho danh sách số. Tìm độ dài dãy con dài nhất sao cho khi xóa một phần tử, các số còn lại xuất hiện cùng số lần.
Ví dụ: numbers = [2, 4, 4, 7, 7, 6, 6] -> 7 (toàn bộ dãy, xóa 2 thì 4,7,6 mỗi số 2 lần).
Duy trì num_freq (tần suất số), freq_freq (tần suất của tần suất), diff_freq (tập tần suất khác 0). Cập nhật dần, kiểm tra điều kiện hợp lệ tại mỗi tiền tố.
Ví dụ
from collections import defaultdict
class Solution:
def solve(self, nums):
num_freq = defaultdict(int)
freq_freq = defaultdict(int)
diff_freq = set()
result = 1
for i, num in enumerate(nums):
cur_freq = num_freq[num]
num_freq[num] += 1
freq_freq[cur_freq] -= 1
freq_freq[cur_freq + 1] += 1
diff_freq.add(cur_freq + 1)
if cur_freq in diff_freq and freq_freq[cur_freq] == 0:
diff_freq.remove(cur_freq)
df_list = list(diff_freq)
if len(df_list) == 1:
result = i + 1
elif (len(df_list) == 2
and any(x == 1 for x in [abs(freq_freq[df_list[0]] - freq_freq[df_list[1]]), freq_freq[df_list[0]], freq_freq[df_list[1]]])
and any(x == 1 for x in [abs(df_list[0] - df_list[1]), df_list[0], df_list[1]])):
result = i + 1
return result
ob = Solution()
print(ob.solve([2, 4, 4, 7, 7, 6, 6]))
Đầu vào
[2, 4, 4, 7, 7, 6, 6]
Đầu ra
7