숫자 쌍을 선택할 수있는 가장 빠른 알고리즘

질문 : N 개의 정수 [N < = 10^5]가 주어지면 K [K> 0 및 K < 1e9] 인 정수의 총 쌍을 계산합니다. N 개의 정수 각각은 0보다 크고 2^31-1부터 K까지 떨어져있을 것입니다 (모든 것은 32 비트 정수로 할 수 있습니다).숫자 쌍을 선택할 수있는 가장 빠른 알고리즘

첫 번째 줄에는 N & K (정수)가 포함됩니다. 두 번째 줄에는 N 개의 숫자가 포함되어 있습니다. 모든 N 개의 숫자는 확실하게 구분됩니다.

이제 문제는 hackerrank입니다. 질문에 대한 해결책이 있지만 모든 샘플 테스트 케이스의 시간 제한을 만족시키지 못합니다. 다른 알고리즘을 사용할 수 있는지는 잘 모르겠지만 아이디어가 없습니다. 누군가 내 코드를 확인하고 팁 또는 두 가지를 줄 때 약간의 시간이 걸리면 정말 감사 할 것입니다.

temp = input() 
temp = temp.split(" ") 
N = int(temp[0]) 
K = int(temp[1]) 
num_array = input() 
num_array = num_array.split(" ") 
diff = 0 
pairs= 0 
i = 0 
while(i < N): 
    num_array[i] = int(num_array[i]) 
    i += 1 
while(num_array != []):  
    j = 0 
    while(j < (len(num_array)-1)): 
     diff = abs(num_array[j+1] - num_array[0]) 
     if(diff == K): 
      pairs += 1 
     j += 1 
    del num_array[0] 
    if(len(num_array) == 1): 
     break 
print(pairs)

출처

2013-10-27 Nwaiwu Gilbert

당신의 절차에 따라 aproximately 선형 시간에이를 수

따라서, O (N) 용액 :

각 번호를 들어 X H [세트 해시에 추가를 그렇다면 X] XK이 H인지 여부를 확인할 수 위해 각 X
- 1 추가 일부 (B)를 사용

OR로 대답 할

이 솔루션은 정수가 구별 인 것으로 가정합니다. 요소 수를 저장해야 할 필요가없는 경우 "집합에 추가 된 수입니다 (예 : 트리 기반 집합) 기본값은 0 "각각에

-"대신 응답 할 하나의 첨가 * H는 [X + K]

그래서, 일반적으로는 일부의 HashMap H을 [X] H의 생성물을 추가 " 숫자 x 업데이트 맵 : H [x] = H [x] +1
각 숫자 x 추가 답변 H [x] * H [xk] H [xk] = 0)

그리고 다시 해시지도를 사용하는 해는 O (n)이고 트리 맵을 사용하여지도에 있는지 여부를 확인할 필요가 없습니다. O (nlgn) numbesr A의

그래서 주어진 및 수 k (고유 한 번호에 대한 솔루션) :

H=set(A) 
ans = sum(1 for a in A if a-k in H) 
print ans

출처

2013-10-27 14:15:48 lejlot

확인. 문제는 만약 당신이 일련의 값을 가지고 있다면, 차이 k를 가진 숫자 쌍의 총수를 찾으십시오. 예 : u가 5 개의 수 : 1 3 5 2 7 ...이고 k = 2 인 경우 쌍은 (1,3) (3,5) (5,7)입니다. 필자의 경우 첫 번째 숫자 (위의 예에서는 "1")를 다른 모든 값과 대조하여 확인합니다. 차이가 있다면, 나는 최종 답에 1을 더한다 .i 다음에 (이전에 체크 된 번호를 생략하고) 다음 값에 대해 같은 작업을한다. 조금 더 나은 방법을 설명 할 수 있습니까? –

@Nwaiwu - 여기서 설명 할 것은 아무것도 없습니다. 제안 된 접근 방식은 각 항목을 통과하고 차이점이있는 항목이 있는지 확인합니다. 전체 "트릭"은이 체크가 선형 시간 대신에 해시 - 세트를 사용하여 일정 시간 (루핑으로 - 솔루션에서와 같이)으로 수행 될 수 있다는 것입니다. – lejlot

@lejlot : 고마워요. 그것은 일했다 :). 한 가지 더 : u가 의미하는 바는 "선형 시간이 아닌 일정 시간 (해시 - 세트 사용)에서 수행 할 수 있습니다 (솔루션 에서처럼 루핑으로)". 나는 파이썬에서 set()을 사용하지 않았다. 어떻게 그렇게 빨리 왔는가? –

H=set() 
ans=0 
for a in A: 
    H.add(a) 
for a in A: 
    if a-k in H: 
    ans+=1 
print ans

이하는 사전 (해시 맵)를 사용합니다.

1 단계 : 사전 D에 배열의 모든 항목을 채 웁니다. 2 단계 : 사전에있는 모든 A [i] + k의 발생을 계산합니다.

Dictionary<int> dict = new Dictionary<int>(); 
foreach (int n in num_array) do dict.Add(n); 
int solitions = 0; 
foreach (int n in num_Array) do 
    if dict.contains(n+k) 
    solutions += 1;

사전 채우기는 O (1)이고, 검색은 O (1)입니다. 배열의 각 요소에 대해이를 수행하는 것은 O (n)입니다. 이것은 가능한 한 빨리입니다.

죄송합니다. 귀하는 그것을 파이썬으로 번역해야합니다.

편집 : 이전 아이디어와 같습니다. 중복해서 죄송합니다. 내 복제본을 삭제하기에는 너무 늦었습니다.

출처

2013-10-27 14:28:53 alzaimar

** 항상 ** 자신의 답변을 삭제할 수 있습니다. – lejlot

숫자 쌍을 선택할 수있는 가장 빠른 알고리즘

답변

관련 문제