Python. Простые алгоритмы

Даны два списка:

a = [1, 2, 3, 4, 5]
b = [2, 1, 5, 3, 4]

Способ 1. Использование сортировки sort()

 Если не важен порядок элементов, то используем сортировку.

n = len(a)
m = len(b)
flag = True
a.sort()
b.sort()
if n!=m:
   flag = False
for i in range(n):
           if (a[i] != b[i]):
               flag = False
              break
print(flag)
# True
Временная сложность: O (n * log n )

Способ 2. Используем множества set()

c = set(a) & set(b)
if len(c) ==len(a):
   print("Yes")
else:
   print("No")

#Yes
Временная сложность O (n * m)

Способ 3. Используем пересечение множеств - intersection().

Метод intersection () (пересечение) возвращает новое множество, содержащее все элементы, которые есть и в первом множестве, и во втором.

c = set(a).intersection(b)
if len(c) ==len(a):
   print("Yes")
else:
   print("No")
# Yes
Временная сложность O (n * m)

Способ 4. Используем Функция zip

Функция zip используется для перебора сразу нескольких объектов одновременно

Если не важен порядок элементов, то используем сортировку. Если порядок элементов важен, то сортировку не используем.

a.sort()
b.sort()
c = [i for i, j in zip(a, b) if i == j]
print(c)
if len(c) == len(a):
   print("Yes")
else:
   print("No")

# Yes
Временная сложность: O (n * log n )

Способ 5. Использование генератора

c = [x for x in a if x in b]
if len(c) == len(a):
   print("Yes")
else:
   print("No")

#Yes
Временная сложность: O (n*m )

Даны два списка:

a = [ 1,2,3,4,5,6]

b = [7,8,9,1,2,3,11,12,12,3]

Способ 1. Использование двух циклов for

n = len(a)
m = len(b)
c=[]
for i in range(n):
     for j in range(m):
         if a[i]== b[j]:
               break
         else:
             if j == m-1:
                 c.append(a[i])
print(c)

# [4, 5, 6]
Временная сложность O (n * m)

Способ 2. Использование операции in

c=[]
for x in a:
     if x not in b:
       c.append(x)
print(c)

# [4, 5, 6]
Временная сложность O (n)

Способ 3. Использование словаря dict()

s = dict()
for i in range(m):
   s[b[i]] = 1
c = []
for i in range(n):
   if a[i] not in s.keys():
       c.append(a[i])
print(c)

# [4, 5, 6]
Временная сложность O(n)

s = 'aa_bb_cc_dd_ee'  # исходная строка
s1 = '_'              # что заменяем
s2 = '/'              # на что заменяем      
s_out=''

Способ №1. Использование метода replace()

s_out = s.replace(s1, s2)
print(s_out)

# aa/bb/cc/dd/ee
Временная сложность: O(n),
n -  длина строки

Способ №2. Использование метода split()

m = s.split('_')   # Разбиваем по разделителю в список подстрок
# print(m)  ['aa', 'bb', 'cc', 'dd', 'ee']
for x in m:
    s_out+=''.join(x)+s2
s_out=s_out[:-1]
print(s_out)

# aa/bb/cc/dd/ee
Временная сложность: O(n)

Способ №3. Использование цикла while

s_out = ""
i = 0
while i < len(s):
    if s[i:i + len(s1)] == s1:
        s_out += s2
        i += len(s1)
    else:
        s_out += s[i]
        i += 1
print(s_out)

 # aa/bb/cc/dd/ee
Временная сложность: O (n*n1),
где n - длина входной строки,
n1 - длина подстроки, подлежащей замене.

s='1234567890'

Способ № 1. Использование цикла for

st =''
for x in s:
    st+=x+' '
print(st)

#1 2 3 4 5 6 7 8 9 0
Временная сложность: O (n)

Способ № 2. Использование метода replace()

s = s.replace('',' ')[1:]
print(s)

#1 2 3 4 5 6 7 8 9 0
Временная сложность: O (n)

Способ № 3. Использование метода split()

m = s.split(' ')
st=''
for x in s:
    st+=x+' '
print(st)

#1 2 3 4 5 6 7 8 9 0
Временная сложность: O (n)

st ="12345abcdefgh114895defgh"

Способ № 1 Использование двойного цикла

k=0
l=''
for i in range (len(st)):
   for j in range (len(st)):
       if st[i] == st[j] and i != j:
                         k+=1
   if k == 0:
       l += st[i]
   else:
       k =0
print(l)

# 23abc89
Временная сложность: O (n*n)

Способ № 2 Использование функций ord и chr

s=[0]*1000
for x in st:
     s[ord(x)]+=1
for i in range (len(s)):
     if s[i] == 1:
       print(chr(i), end = "")

# 2389abc
Временная сложность: O (n*n1)
где n - длина входной строки,
n1 - длина списка s

Способ № 3 Использование метода count()

m=[]
for x in st:
     if x not in m and st.count(x) == 1:
           m.append(x)
           print("".join(x), end ='')

# 23abc89
Временная сложность: O (n)

Способ № 4 Использование функции lambda()

m = filter(lambda x: st.count(x) == 1, st)
print(''.join(set(m)))

#89ac3b2
Временная сложность: O (n)

Способ № 5 Использование словаря и множества

d={x: st.count(x) for x in sorted(set(st))} # создаем словарь

# проходим по словарю и определяем ключ значения ==1
for x in d:      

   if d[x] == 1:
       print(x, end = '')

# 2389abc
Временная сложность: O (n)