Как указано выше, мне нужно эффективно подсчитать количество различных троек формы (a, b, b). Кроме того, тройка действительна только тогда и только тогда, когда ее можно сформировать путем удаления некоторых целых чисел из массива, оставив после себя только эту тройку в этом конкретном порядке. Я считаю, что это говорит о том, что тройки должны располагаться в хронологическом порядке, но не обязательно состоять из последовательных элементов. Решение должно быть действительно эффективным, поскольку N (длина массива) может достигать 10^6 (или миллиона). Например, если массив был [5, 6, 7, 3, 3, 3], то ответом будет 3, поскольку тройки будут такими: (5, 3, 3), (6, 3, 3) и (7, 3, 3).
Это был мой первый перебор (для начала, O(n^3)):
Код: Выделить всё
n = int(input())
arr = list(map(int, input().split()))
ans = set()
for i in range(n):
for j in range(i + 1, n):
if arr[i] != arr[j]:
for k in range(j + 1, n):
if arr[j] == arr[k]:
ans.add((arr[i], arr[j], arr[k]))
print(len(ans))
Тогда я безуспешно пытался оптимизировать это на O (n^2), что все еще слишком медленно, но я даже не могу понять это правильно: < Br />
Код: Выделить всё
def solve():
n = int(input())
arr = list(map(int, input().split()))
freq = Counter(arr)
ans = set()
for a in freq:
if freq[a] < 1:
continue
for b in freq:
if b != a and freq[b] >= 2:
ans.add((a, b, b))
return len(ans)
print(solve())
Я не могу исправить логику для O(n^2) и оптимизировать ее, чтобы полностью решить проблему при заданных ограничениях. Помощь будет очень признательна.
Подробнее здесь:
https://stackoverflow.com/questions/793 ... are-of-the
Мобильная версия