효율적인 알고리즘 제안

Question

배열 arr 크기가 100000 인 경우 각 요소 0 <= arr[i] < 100이 제공됩니다.

는 (i,j,k)이 존재 얼마나 많은 세 쌍둥이 알아 (정렬되지, 중복 포함) 등이 arr[i]^arr[j]^arr[k] == 0 주 : ^는 XOR 연산자됩니다. 또한 0 <= i <= j <= k <= 100000

주파수를 계산하고 주파수를 사용하여 계산해야한다는 느낌이 들지만, 시작하지 못하는 것 같습니다.

명백한 O(n^3)보다 나은 알고리즘은 언제나 환영합니다. :)

숙제가 아닙니다. :)

Answer 1

나는 키가 당신이 얼마나 많은 I, J, K, 단지 계산 식별 할 필요가 없습니다 생각합니다. 트리플 어떤 운동의 작은 어레이의 비 - 제로 엘리먼트를 통해 O (N)

루프 -

얼마나 많은 각각의 값을 계산하지만 도착 배열 크기 100

루프를 초기화한다 조건을 만족시킵니다 - 관련된 세 개의 숫자의 수를 A, B, C로 가정하십시오 - 원래 arr의 조합 수는 (A + B + C) /! A! B! C! - 100 ** 3 연산이지만 100이 고정 값이라고 가정 할 때 여전히 O (1)입니다.

그래서, O (n).

Answer 2

Sort the array, keeping a map of new indices to originals. O(nlgn) 
Loop over i,j:i<j. O(n^2) 
    Calculate x = arr[i]^arr[j] 
    Since x^arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn) 
    For all found k, print mapped i,j,k 

O (N^2 LGN)

Answer 3

가능한 경우 가능한 O (n^2) 솔루션 : 변수 count과 두 개의 배열 single[100] 및 pair[100]을 유지하십시오. arr를 반복하고, 값 n의 각 요소 :

• 업데이트 count : count += pair[n]
• 업데이트 pair : 대하여 반복 배열 single 인덱스 x 가치의 각 요소 s != 0는 pair[s^n] += single[x]
• 업데이트 single을 수행 single[n]++을

결국 count 결과가 저장됩니다.

Answer 4

폴 (Paul)이 제안한대로 1에서 100 사이의 각 숫자의 빈도 카운트부터 시작하십시오. 그러면 길이 100의 배열 freq []가 생성됩니다.

다음으로, 배열에서 트리플 A, B, C를 반복하고 A^B^C = 0 조건을 테스트하는 대신, A, B 쌍의 루프 A, B를 반복합니다. A < B. 각각의 A, B에 대해 C = A^B를 계산하여 (이제 A^B^C = 0이되도록) A < B < C < 100을 확인하십시오 (임의의 순서로 모든 트리플이 발생합니다. 이것은 트리플을 놓치지 않습니다.하지만 아래 참조).세 다른 번호의 모든 트리플 이후 < B.

위에 루프에 대해 5000 워크는 주파수 카운트 (N) O이다

Sum+=freq[A]*freq[B]*freq[C] 

플러스 : 누적 합계는 같을 것이다 A, B, C가 어떤 순서로 발생해야합니다. 이렇게하면 각 트리플을 정확히 한 번 찾습니다. 다음으로 두 숫자가 같은 트리플을 찾아야합니다. 그러나 두 숫자가 같고 세 개 중 xor가 0이면 세 번째 숫자는 0이어야합니다. 따라서 이것은 빈도 카운트 배열에 대한 B에 대한 2 차 선형 검색으로 발생합니다 (A = 0, B = C < 100). (이 경우에 특히주의를 기울여야하며 특히 B = 0 인 경우주의하십시오. 카운트는 단지 주파수 [B] ** 2 또는 주파수 [0] ** 3이 아닙니다. 3. 거기에 약간의 조합 문제가 숨어 있습니다.)

희망이 도움이됩니다.

Answer 5

가능한 O (100 * n) = O (n) 용액. 문제를 해결합니다 < = j < = k. 아시다시피^B = 0 < => A = B A, 내 나쁜 영어 때문에

long long calcTripletsCount(const vector<int>& sourceArray) 
{ 
    long long res = 0; 
    vector<int> count(128); 
    vector<int> countPairs(128); 
    for(int i = 0; i < sourceArray.size(); i++) 
    { 
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++) 
     countPairs[j^sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i]^sourceArray[j] 
    res += countPairs[sourceArray[i]]; // a^b^c = 0 if a^b = c, we add count of pairs (p1, p2) where sourceArray[p1]^sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i) 
    } 
    return res; 
} 

죄송합니다 ... 나는 (N^2 로그 n)은 (단순) O가

Answer 6

i, j 및 k는 정수가 아니라 인덱스를 참조한다는 사실을 고려한 솔루션입니다.

간단한 첫 번째 단계를 통해 100 개의 값으로 구성된 배열 A를 만들 수 있습니다. 값 -> 인덱스 목록 - 나중에 사용하기 위해 정렬 된 목록을 유지합니다. O (nlog n)

각 쌍 i, j가 i < = j 일 때, X = arr [i]^arr [j]를 계산한다. 그런 다음 A> [X]에서 이진 검색을 수행하여 k> = j가되는 인덱스 k의 수를 찾습니다. O (n^2 log n)

색인 요구 사항을 몰아 내기 때문에 분류/계산 알고리즘을 활용할 수있는 방법을 찾지 못했습니다.