Пары, имеющие похожие элементы - PullRequest
Новая
       6

Пары, имеющие похожие элементы

0 голосов
/ 29 сентября 2019

Для данного массива A, имеющего N целых чисел A1, A2, ..., An. Два элемента массива Ai и Aj называются аналогичными, если Ai = Aj +1 или Aj = Ai +1. Кроме того, сходство следуеттранзитивность.Если Ai и Aj схожи, а Aj и Ak схожи, то Ai и Ak также схожи. Ниже приведен мой код с дополнительной сложностью времени. Как мы можем уменьшить его? 

def SimilarElementsPairs (A,N):
  # Write your code here
  count=0
  map1=[]
  for i in range(0,N):
      for j in range(0,N):
          if((A[i]==A[j]+1) or (A[j]==A[i]+1)):
                  count+=1
                  map1.append((i,j))
          for k in range(0,N):
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[k]==A[j]+1) or (A[j]==A[k]+1))))  :
                  count+=1
                  map1.append((i,k))
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[j]==A[k]+1) or (A[k]==A[j]+1)))):
                  count+=1
                  #map1.append((i,k))
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[k]==A[i]+1) or (A[i]==A[k]+1)))):
                  count+=1
                  map1.append((j,k))
  list1 = set(map(lambda x: tuple(sorted(x)),map1))
  list2=[]
  for x,y in list1:
      if abs(x-y)>0:
          list2.append((x,y))
  return len(list2)

N = input()
A = map(int, raw_input().split())
out_ = SimilarElementsPairs(A,N)
print out_
...