У меня есть эта функция для определения того, является ли список поворотным списком другого списка:
def isRotation(a,b):
if len(a) != len(b):
return False
c=b*2
i=0
while a[0] != c[i]:
i+=1
for x in a:
if x!= c[i]:
return False
i+=1
return True
например.
>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True
Как мне сделать эту работу с дубликатами? например
a = [3,1,2,3,4]
b = [3,4,3,1,2]
И можно ли это сделать в O(n) времени?
Вы можете сделать это в пространстве 0(n) и 0(1) с помощью модифицированной версии алгоритма максимальных суффиксов:
Из Драгоценности стробоскопии: Циклическое равенство слов
Вращение слова u длины n является любым словом вида u [k + 1... n] [l... k]. Пусть u, w - два слова одной длины n. Они называются циклически эквивалентными, если u (i) == w (j) для некоторых i, j.
Если слова u и w записаны в виде кругов, они являются циклически эквивалентными, если круги после соответствующих вращений совпадают.
Существует несколько алгоритмов линейного времени для проверки циклической эквивалентности двух слов. Самый простой из них - применить любой алгоритм соответствия строк к шаблону pat = u и text = ww, потому что слова u и w являются циклическими = эквивалентными, если pat имеет место в тексте.
Другой алгоритм - найти максимальные суффиксы uu и ww и проверить, если они одинаковы на префиксах размера n. Мы выбрали эту проблему, потому что есть более простой интересный алгоритм, работающий в линейном времени и постоянном пространстве одновременно, который заслуживает презентации.
Algorithm Cyclic-Equivalence(u, w)
{ checks cyclic equality of u and w of common length n }
x := uu; y := ww;
i := 0; j := 0;
while (i < n) and (j < n) do begin
k := 1;
while x[i + k] = y[j + k] do k := k + 1;
if k > n then return true;
if x[i + k]> y[i + k] then i := i + k else j := j + k;
{ invariant }
end;
return false;
Какой перевод на python будет выглядеть следующим образом:
def cyclic_equiv(u, v):
n, i, j = len(u), 0, 0
if n != len(v):
return False
while i < n and j < n:
k = 1
while k <= n and u[(i + k) % n] == v[(j + k) % n]:
k += 1
if k > n:
return True
if u[(i + k) % n] > v[(j + k) % n]:
i += k
else:
j += k
return False
Запуск нескольких примеров:
In [4]: a = [3,1,2,3,4]
In [5]: b =[3,4,3,1,2]
In [6]: cyclic_equiv(a,b)
Out[6]: True
In [7]: b =[3,4,3,2,1]
In [8]: cyclic_equiv(a,b)
Out[8]: False
In [9]: b =[3,4,3,2]
In [10]: cyclic_equiv(a,b)
Out[10]: False
In [11]: cyclic_equiv([1,2,3],[1,2,3])
Out[11]: True
In [12]: cyclic_equiv([3,1,2],[1,2,3])
Out[12]: True
Более наивный подход состоял бы в том, чтобы использовать collection.deque для поворота элементов:
def rot(l1,l2):
from collections import deque
if l1 == l2:
return True
# if length is different we cannot get a match
if len(l2) != len(l1):
return False
# if any elements are different we cannot get a match
if set(l1).difference(l2):
return False
l2,l1 = deque(l2),deque(l1)
for i in range(len(l1)):
l2.rotate() # l2.appendleft(d.pop())
if l1 == l2:
return True
return False
Этот мета-алгоритм разрешит его.
Создайте конкатенацию a, например, a = [3,1,2,3,4] = > aa = [3,1,2,3,4,3,1,2,3,4].
Запустите любую адаптацию строки алгоритма сопоставления строк, например Boyer Moore, чтобы найти b в aa.
Одной из особенно простых реализаций, которую я хотел бы попробовать, является использование Рабина Карпа в качестве основного алгоритма. В этом случае вы
вычислить Отпечаток Rabin для b
вычислить отпечаток Rabin для aa[: len(b)], aa[1: len(b) + 1],... и сравнить списки только тогда, когда отпечатки пальцев соответствуют
Обратите внимание, что
Отпечаток пальца Рабина для скользящего окна может быть рассчитан итеративно очень эффективно (читайте об этом по ссылке Рабина-Карпа)
Если ваш список целых чисел, у вас на самом деле есть немного более легкое время, чем для строк, так как вам не нужно думать, что такое числовое хеш-значение буквы
-Я думаю, вы могли бы использовать что-то вроде этого:
a1 = [3,4,5,1,2,4,2]
a2 = [4,5,1,2,4,2,3]
# Array a2 is rotation of array a1 if it sublist of a1+a1
def is_rotation(a1, a2):
if len(a1) != len(a2):
return False
double_array = a1 + a1
return check_sublist(double_array, a2)
def check_sublist(a1, a2):
if len(a1) < len(a2):
return False
j = 0
for i in range(len(a1)):
if a1[i] == a2[j]:
j += 1
else:
j = 0
if j == len(a2):
return True
return j == len(a2)
Просто здравый смысл, если мы говорим о вопросах интервью:
В качестве альтернативы (я не мог заставить решение b in aa работать), вы можете "повернуть" свой список и проверить, равен ли повернутый список b:
def is_rotation(a, b):
for n in range(len(a)):
c = c = a[-n:] + a[:-n]
if b == c:
return True
return False
Я считаю, что это будет O (n), поскольку он имеет только один цикл for. Надеюсь, что это поможет.
Кажется, что это работает.
def func(a,b):
if len(a) != len(b):
return False
elif a == b:
return True
indices = [i for i, x in enumerate(b) if x == a[0] and i > 0]
for i in indices:
if a == b[i:] + b[:i]:
return True
return False
И это также:
def func(a, b):
length = len(a)
if length != len(b):
return False
i = 0
while i < length:
if a[0] == b[i]:
j = i
for x in a:
if x != b[j]:
break
j = (j + 1) % length
return True
i += 1
return False
Если вы можете представить их как строки вместо этого, просто выполните:
def cyclically_equivalent(a, b):
return len(a) == len(b) and a in 2 * b
В противном случае нужно получить алгоритм поиска подписок, такой как Knuth-Morris-Pratt (Google дает некоторые варианты реализации) и
def cyclically_equivalent(a, b):
return len(a) == len(b) and sublist_check(a, 2 * b)
Вы можете попробовать проверить производительность только с помощью функции rotate() в коллекции deque:
from collections import deque
def is_rotation(a, b):
if len(a) == len(b):
da = deque(a)
db = deque(b)
for offset in range(len(a)):
if da == db:
return True
da.rotate(1)
return False
Что касается производительности, вам нужно сделать этот расчет много раз для небольших массивов или несколько раз на очень больших массивах? Это позволит определить, ускорит ли его тестирование.
алгоритм Knuth-Morris-Pratt - это строковый алгоритм поиска, который работает в O (n), где n - длина текста S ( предполагая существование предварительно построенной таблицы T, которая выполняется в O (m), где m - длина строки поиска). В целом это O (n + m).
Вы можете сделать аналогичный алгоритм сопоставления шаблонов, созданный KMP.
a+a или b+b - это искомый текст/список с 2 * n элементамиb или a) - это выполняется в O (n)Общая временная сложность O (2 * n + n) = O (3 * n), которая находится в O (n)