Блог

Я столкнулся с проблемой и, похоже, не могу найти эффективного решения. Проблема заключается в следующем:

Учитывая массив A, подсчитайте количество последовательных непрерывных подмассивов таким образом, чтобы каждый элемент в подмассиве появлялся по крайней мере дважды.

Например, для:

 A = [0,0,0]
 

Ответ должен быть 3, потому что у нас есть

 A[0..1] = [0,0]
A[1..2] = [0,0]
A[0..3] = [0,0,0]
 

Другой пример:

 A=[1,2,1,2,3]
 

Ответ должен быть 1, потому что у нас есть:

 A[0..3] = [1,2,1,2]
 

Кажется, я не могу придумать эффективного решения для этого алгоритма. У меня есть алгоритм, который проверяет все возможные подмассивы (O (n ^ 2)), но мне нужно что-то получше. Это мое наивное решение:

 def duplicatesOnSegment(arr):
    total = 0
    for i in range(0,len(arr)):
        unique = 0
        test = {}
        for j in range(i,len(arr)):
            k = arr[j]
            if k not in test:
                test[k] = 1
            else:
                test[k]  =  1

            if test[k] == 1:
                unique  = 1
            elif test[k] == 2:
                unique -= 1
            if unique == 0:
                total  = 1
    return total
 

Ваша программа в худшем случае больше O (n ^ 2), поскольку вы используете if k not in test во вложенном цикле. in В худшем случае это O (n), что приводит к общему наихудшему случаю O (n ^ 3). У меня есть это, O (n ^ 2) в худшем случае, решение, которое использует collections.defaultdict как хэш, чтобы ускорить это.

 from collections import defaultdict

def func(A):
    result = 0
    for i in range(0,len(A)):
        counter = 0
        hash = defaultdict (int)
        for j in range (i, len(A)):
            hash[A[j]]  = 1
            if hash[A[j]] == 2:
                counter  = 1
            if counter != 0 and counter == len(hash):
                result  = 1
    return result
 

Для начала я бы рассмотрел отрицание интересующего свойства :

not(all(x in l appears at least twice)) = exists(x in l such that any other y in l != x)

Пока не уверен, что предыдущая переформулировка вашего вопроса может помочь, но моя интуиция как математика подсказала мне попробовать этот способ… Тем не менее, все равно похоже на O (n ^ 2)…

 my_list = ['b', 'b', 'a', 'd', 'd', 'c']

def remaining_list(el,list):
    assert el in list
    if el == list[-1]: return []
    else: return list[list.index(el) 1:]

def has_duplicate(el, list):
    assert el in list
    return el in remaining_list(el,list)

list(filter(lambda e:not(has_duplicate(e,my_list)),my_list))