ให้ลิสต์ตัวเลข หาความยาว prefix ยาวที่สุด ที่เมื่อลบตัวเลข 1 ตัวออก จะทำให้ทุกตัวเลขที่เหลือมีความถี่เท่ากัน
ตัวอย่าง: [2, 4, 4, 7, 7, 6, 6] → 7 (ลบ 2 ออก เหลือ 4,4,7,7,6,6 ทุกตัวมีความถี่ 2)
อัลกอริธึม
- ใช้
num_freqนับความถี่แต่ละตัวเลข - ใช้
freq_freqนับว่ามีตัวเลขกี่ตัวที่มีความถี่เท่ากัน - ใช้
diff_freqเก็บความถี่ที่มีอยู่จริง - ตรวจสอบเงื่อนไข: ถ้ามีความถี่ชนิดเดียว หรือ 2 ชนิดที่ต่างกัน 1 และจำนวนตัวเลขต่างกัน 1 → valid
การนำไปใช้
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])) # 7
