주어진 합계로 쌍을 열거하는 데 더 나은 알고리즘 (dict 사용보다).

Question

숫자가 주어지면, 그 총합이 그 숫자와 같은 배열에서 가능한 모든 인덱스 쌍을 찾아야합니다. 현재 다음 알 고를 사용 중입니다.

def myfunc(array,num): 
    dic = {} 
    for x in xrange(len(array)): # if 6 is the current key, 
     if dic.has_key(num-array[x]): #look at whether num-x is there in dic 
      for y in dic[num-array[x]]: #if yes, print all key-pair values 
       print (x,y), 
     if dic.has_key(array[x]): #check whether the current keyed value exists 
      dic[array[x]].append(x) #if so, append the index to the list of indexes for that keyed value 
     else: 
      dic[array[x]] = [x] #else create a new array 

O(N) 시간에 실행됩니까? 그렇지 않다면 무엇을해야 그렇게 할 수 있습니까? 그리고 어떤 경우 든 보조 데이터 구조를 사용하지 않고 O(N) 시간에 실행할 수 있습니까?

Answer 1

O (N) 시간에 실행됩니까?

예 아니오. 복잡성은 실제로 O(N + M)이고 M은 출력 크기가입니다.
아쉽게도 출력 크기는 O(N^2)입니다. 예를 들어 배열 [3,3,3,3,3,...,3] 및 number == 6과 같이 최악의 경우입니다. 생산에 필요한 요소의 수가 2 진수가됩니다.

그러나 점진적으로 말하자면 입력 크기와 출력 크기가 선형이기 때문에 더 잘 수행 할 수 없습니다.

Answer 2

배열 참조를 사용하여 O (N) 시간에 실제로 실행되는 매우 간단한 솔루션입니다. 모든 출력 쌍을 열거하려면, 물론 (amit 음으로) 최악의 경우 O (N^2)를 취해야합니다.

from collections import defaultdict 
def findpairs(arr, target): 
    flip = defaultdict(list) 
    for i, j in enumerate(arr): 
     flip[j].append(i) 
    for i, j in enumerate(arr): 
     if target-j in flip: 
      yield i, flip[target-j] 

후 처리는 출력 값을 모두 얻을 수 (및 (i,i) 답변을 걸러 일) :

def allpairs(arr, target): 
    for i, js in findpairs(arr, target): 
     for j in js: 
      if i < j: yield (i, j) 

Answer 3

이 도움이 될 - Optimal Algorithm needed for finding pairs divisible by a given integer k

(약간의 수정과 함께, 거기에 우리가보고있다 모든 숫자는 주어진 숫자로 나눌 수 있으며 반드시 주어진 숫자와 같을 필요는 없습니다.)