java - left - juggling algorithm for array rotation




O(n)에있는 배열의 모든 차이점 찾기 (4)

질문 : 정렬 된 배열 A에서 가능한 모든 요소의 차이점을 찾습니다.

내 솔루션 :

for (int i=0; i<n-1; ++i) {
  for (int j=i+1; j<n; ++j) {
    System.out.println(Math.abs(ai-aj));
  }
}

물론, 그것은 O (n ^ 2)이지만, 나는 물건을 세어 계산하지 않습니다. 나는 온라인으로 봤는데 나는 이것을 발견했다 : http://www.careercup.com/question?id=9111881 . 그것은 당신이 더 잘할 수 없다고 말하지만, 인터뷰에서 나는 O (n) 할 수 있다고 들었습니다. 어느 것이 맞는지?


면접관이 이론적 인 게임을 좋아한다면 그는 아마도 입력 및 결과 테이블을 사용하려고 생각하고있을 것입니다. 입력 크기에 제한이 있고 알려진 솔루션이있는 문제는 테이블 조회를 통해 해결할 수 있습니다. 주어진 테이블을 처음 생성하여 저장 했으므로 테이블 일 수 있습니다.

따라서 배열 크기가 제한된 경우 테이블 조회를 통해 문제를 해결할 수 있습니다. 일부 가정에서는 일정 시간 내에 완료 할 수도 있습니다. 물론 최대 배열 크기가 2 인 경우 (32 비트 정수라고 가정) 테이블은 일반 컴퓨터의 메모리 또는 디스크에 맞지 않습니다. 배열의 더 큰 최대 크기의 경우 "알려진 우주에 맞지 않습니다"크기가됩니다. 그러나 이론적으로는 가능합니다.

(그러나 사실, Jens Gustedt의 의견은 더 많은 것으로 생각됩니다.)


예를 들어, 요소가 {2 1 , 2 2 , ..., 2 n } 인 배열의 경우 n • (n-1) / 2 개의 가능한 차이가 있으며 둘 중 어느 것도 동일하지 않습니다. 따라서 O (n 2 ) 차이가 있습니다.

그들 모두를 열거해야하기 때문에 적어도 O (n 2 ) 시간이 필요합니다.


정렬하기 전에 배열 내용이 임의의 정수라고 가정하여 또 다른 카운터 예제를 얻을 수 있습니다. 그러면 Ai - Aj 대 Ak - Al, 또는 심지어 Ai - Aj 대 Aj - Ak의 두 가지 차이가 ​​동일 할 확률이 너무 작아 O (n) 개의 뚜렷한 차이 Ai - Aj 만 존재할 가능성이 없습니다.

그 점을 감안할 때, 당신의 면접관에게하는 질문은 O (n) 해를 허용하는 특별한 상황을 설명하는 것입니다. 한 가지 가능성은 배열 값이 0..n 범위의 모든 숫자입니다.이 경우 최대 절대 차이는 n이기 때문입니다.

나는 O (ng n)에서 이것을 할 수 있지만 O (n)에서는 할 수 없다. 배열에 값 i가있는 요소 i를 1로 설정하고 크기 n + 1의 배열로 배열 내용을 나타냅니다. 그런 다음 FFT를 사용하여 배열 자체를 컨볼 루션합니다. 컨벌루션의 k 번째 요소가 0이 아니라면 Ai - Aj = k의 차이가 있습니다.


첫 번째 생각은 배열이 정렬된다는 사실을 사용하지 않는다는 것입니다. 증가 순서에 있다고 가정 해 봅니다 (감소는 유사하게 처리 될 수 있음).

우리는 또한 차이 망원경 (i> j)이라는 사실을 사용할 수 있습니다 :

a_i - a_j = (a_i - a_(i-1)) + (a_(i-1) - a_(i-2)) + ... + (a_(j+1) - a_j)

이제 새 시퀀스를 작성하여 s라고 부르십시오.이 시퀀스는 간단한 차이 (의미 (a_i - a_(i-1)) 집니다. 이 작업은 단 하나의 패스 ( O(n) )를 수행하며, 반복을 건너 뛸 수도 있습니다. a_i = a_(i+1) 경우 a_i = a_(i+1) 건너 뛸 수 있습니다.

모든 가능한 차이 a_i-a_ji>js_i + s_(i+1) + ... + s_(j+1) 입니다. 어쩌면 당신이 그들을 발견 한 것으로 간주한다면 O(n) 시간에 그것을했습니다. 그러나 인쇄하려면 n(n-1)/2 호출만큼 많은 시간이 걸릴 수 있으며 그 것은 O(n^2) 입니다.







algorithm