정렬된 배열에서 O(n) 시간에 홀수 번 발생하는 숫자를 어떻게 찾을 수 있습니까?

정렬된 배열에서 O(n) 시간에 홀수 번 발생하는 숫자를 어떻게 찾을 수 있습니까?

질문이 하나 있는데 몇 번이고 다시 생각해봤는데...질문을 여기에 올리는 것은 아무것도 없습니다.내가 다른 사람들의 관점을 좀 얻을 수 있을지도 모르고, 그것이 잘 되도록 노력할 수 있을지도...

문제는 우리에게 정렬된 배열이 주어지며, 이 배열은 홀수의 홀수를 제외하고 짝수의 값이 발생하는 집합으로 구성된다는 것입니다.우리는 로그인 시간 내에 해결책을 찾아야 합니다.

O(n) 시간에 솔루션을 찾는 것은 쉽지만, 로그인 시간에 수행하는 것은 매우 까다로워 보입니다.

정리:이 문제에 대한 모든 결정론적 알고리즘은 최악의 경우 Δ(log² n) 메모리 위치를 조사합니다.

증명(더 공식적인 스타일로 완전히 다시 작성됨):

k > 0이 홀수 정수이고 n = k라고² 합니다.우리는 (로그₂(k + 1)² = Δ(로그² n) 프로브를 강제하는 적수를 설명합니다.

우리는 동일한 요소 그룹의 최대 연속성을 부릅니다.상대편의 가능한 입력은 k length-k 세그먼트₁₂ x … x로_k 구성됩니다. 각 세그먼트_j x에 대해 x는 j - 1의 b 복사본과 j의 k - b_j 복사본으로 구성되는_jj 정수_j b ∈ [0, k]가 존재합니다.각 그룹은 최대 두 개의 세그먼트와 겹치고 각 세그먼트는 최대 두 개의 그룹과 겹칩니다.

Group boundaries
|   |     |   |   |
 0 0 1 1 1 2 2 3 3
|     |     |     |
Segment boundaries

두 개가 증가하는 곳이면 어디든 관례에 따라 이중 경계를 가정합니다.

Group boundaries
|     ||       |   |
 0 0 0  2 2 2 2 3 3

청구항: j군^th 경계(1 ≤ j ≤ k)의 위치는 세그먼트_j x에 의해 고유하게 결정됩니다.

증명: (j - 1) k + ^thb_j) 메모리 위치 직후이며, x는 b_j. //를 고유하게 결정합니다_j.

우리는 알고리즘이 x에 대한_j 프로브의 결과가 x를 고유하게_j 결정할 경우에 대비하여 j 그룹^th 경계를 관찰했다고 말합니다. 관례에 따라 입력의 시작과 끝은 항상 관찰됩니다.알고리즘은 그룹 경계를 관찰하지 않고 그룹 경계의 위치를 고유하게 결정할 수 있습니다.

Group boundaries
|   X   |   |     |
 0 0 ? 1 2 2 3 3 3
|     |     |     |
Segment boundaries

0 ?만 주어지면 알고리즘은 ?가 0인지 1인지 확실히 알 수 없습니다.그러나 문맥상으로 ?는 반드시 1이어야 하며, 그렇지 않으면 홀수 그룹이 세 개 있을 것이며, X의 그룹 경계를 추론할 수 있습니다.이러한 추론은 상대방에게 문제가 될 수 있지만, 문제의 그룹 경계가 "관련이 없는" 경우에만 가능한 것으로 드러났습니다.

주장: 알고리즘이 실행되는 동안 주어진 지점에서 알고리즘이 관찰한 그룹 경계 집합을 고려합니다. 연속된 한 쌍이 홀수 거리에 있고 홀수 그룹이 그 사이에 있습니다.

증명: 다른 모든 연속 쌍은 짝수 그룹만 제한합니다. //

특수 연속 쌍에 의해 경계가 지정된 홀수 길이 연속을 관련 연속으로 정의합니다.

주장: 관련된 후속 작업 내부의 어떤 그룹 경계도 고유하게 결정되지 않았습니다. 이러한 경계가 하나 이상 있는 경우 홀수 그룹의 동일성은 고유하게 결정되지 않습니다.

증명: 일반성의 손실 없이, 관련 시퀀스에 포함되지 않은 각 메모리 위치가 프로빙되었다고 가정하고, 해당 시퀀스에 포함된 각 세그먼트가 프로빙되지 않은 위치를 정확히 하나만 가지고 있다고 가정합니다.j^th 그룹 경계(B라고 함)가 관련 순서의 내부에 있다고 가정합니다.가설에 따르면 x에 대한_j 프로브는 최대 두 개의 연속 가능성까지 B의 위치를 결정합니다.우리는 관찰된 왼쪽 경계로부터 홀수 거리에 있는 것을 홀수-왼쪽 경계와 다른 홀수-오른쪽 경계라고 부릅니다.두 가지 가능성 모두 왼쪽에서 오른쪽으로 작업하고 나머지 모든 내부 그룹 경계의 위치를 고정하여 왼쪽 그룹이 균등하도록 합니다. (각각 두 개의 연속적인 가능성도 있기 때문에 이 작업을 수행할 수 있습니다.B가 홀수 왼쪽에 있으면 왼쪽에 있는 그룹이 고유 홀수 그룹입니다.B가 홀수 오른쪽에 있으면 관련 순서의 마지막 그룹이 고유 홀수 그룹입니다.둘 다 유효한 입력이므로 알고리즘은 B나 홀수 그룹의 위치를 고유하게 결정하지 않았습니다. //

예:

Observed group boundaries; relevant subsequence marked by […]
[             ]   |
 0 0 Y 1 1 Z 2 3 3
|     |     |     |
Segment boundaries

Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1

이 주장의 결과로, 알고리즘은 작동 방식에 관계없이 관련 순서를 하나의 그룹으로 좁혀야 합니다.따라서 정의에 따라 일부 그룹 경계를 준수해야 합니다.적수는 이제 가능한 한 많은 가능성을 열어두는 간단한 임무를 가지고 있습니다.

알고리즘이 실행되는 동안 지정된 시점에서 공격자는 내부적으로 관련 후속 작업 이외의 각 메모리 위치에 대해 하나의 가능성을 커밋합니다.처음에는 관련 순서가 전체 입력이므로 초기 약속은 없습니다.알고리즘이 x의_j 커밋되지 않은 위치를 탐색할 때마다 상대는 두 값(j - 1 또는 j) 중 하나로 커밋해야 합니다.j^th 경계가 관측되지 않도록 할 수 있는 경우 관측치와 관련하여 나머지 가능성의 절반 이상을 남기는 값을 선택합니다.그렇지 않으면 그룹의 절반 이상을 관련 간격으로 유지하도록 선택하고 나머지 값을 커밋합니다.

이러한 방식으로, 상대는 알고리즘이 적어도 로그₂(k + 1) 그룹 경계를 관찰하도록 강제하고, j 그룹^th 경계를 관찰할 때 알고리즘은 적어도 로그₂(k + 1) 프로브를 만들도록 강제합니다.

---

확장:

이 결과는 입력을 무작위화하고, "최대 절반"(알고리즘 관점에서)을 "최대 절반"으로 대체하고, 표준 농도 부등식을 적용함으로써 무작위 알고리듬으로 바로 확장됩니다.

또한 복사본보다 큰 그룹이 없을 경우에도 확장됩니다. 이 경우 하한은 Δ(로그 n개)입니다.

정렬된 배열은 이진 검색을 제안합니다.우리는 평등과 비교를 재정의해야 합니다.등식 단순은 홀수의 원소를 의미합니다.우리는 그룹의 첫 번째 또는 마지막 요소의 인덱스를 관찰하여 비교할 수 있습니다.첫 번째 요소는 홀수 그룹 앞에 짝수 인덱스(0 기반)가 되고 홀수 그룹 뒤에 홀수 인덱스가 됩니다.이진 검색을 사용하여 그룹의 첫 번째와 마지막 요소를 찾을 수 있습니다.총 비용은 O(로그 N)²입니다.

증명 O((로그 N)²)

  T(2) = 1 //to make the summation nice
  T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements

일부 N=2^k의 경우,

T(2^k) = (log 2^k) + T(2^(k-1))
       = (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
       = (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
       = k + (k-1) + (k-2) + ... + 1
       = k(k+1)/2
       = (k² + k)/2
       = (log(N)² + log(N))/ 2
       = O(log(N)²)

배열의 중간 요소를 확인합니다.몇 가지 적절한 이진 검색을 사용하면 배열에서 처음과 마지막 모양을 찾을 수 있습니다.예를 들어, 중간 요소가 'a'이면 다음을 찾아야 합니다.i그리고.j아래와 같이:

[* * * * a a a a * * *]
         ^     ^ 
         |     |
         |     |
         i     j

아이즈j - i짝수?당신은 해냈어요!그렇지 않으면 (그리고 이것이 여기서 핵심입니다) 질문은 i가 짝수입니까, 아니면 홀수입니까?당신은 이 지식이 무엇을 의미하는지 아십니까?그럼 나머지는 쉬워요.

이 답변은 "폐기 행위"에 의해 게시된 답변을 지지하는 것입니다.그는 현상금을 받을 자격이 있습니다.저는 이 질문에 시간을 할애했고 홀수 발생 횟수를 찾기 위해 Δ(log(n)^2) 쿼리가 필요하다는 그의 증거가 맞다고 확신합니다.저는 그의 해결책을 대충 훑어본 후에 똑같은 주장을 반복하게 되었기 때문에 확신합니다.

솔루션에서, 적수는 알고리즘의 삶을 어렵게 만들기 위해 입력을 생성하지만 인간 분석가에게는 단순합니다.입력은 각각 k개의 항목이 있는 k개의 페이지로 구성됩니다.총 항목 수는 n = k^2이며, O(log(k) = O(log(n)) 및 Δ(log(k) = Δ(log(n))가 중요합니다.입력을 하기 위해, 상대는 임의의 위치에서 전환과 함께 00...011...1 형식의 길이 k의 문자열을 만듭니다.그런 다음 문자열의 각 기호가 aa...abb...b 형식의 길이 k 페이지로 확장됩니다. 여기서 i번째 페이지에서는 a=i 및 b=i+1입니다.패리티가 페이지를 확장한 기호와 일치한다는 점을 제외하고는 각 페이지의 전환도 임의의 위치에 있습니다.

알고리즘의 최악의 경우를 분석하는 "반대 방법"을 이해하는 것이 중요합니다.상대방은 알고리즘의 입력에 대한 질문에 답변하고 이후 답변을 커밋하지 않습니다.답은 일관성이 있어야 하며, 알고리즘이 결론에 도달할 수 있을 정도로 상대가 고정되어 있을 때 게임이 종료됩니다.

이러한 배경을 바탕으로 다음과 같은 몇 가지 관찰 결과가 있습니다.

해당 페이지에서 쿼리를 수행하여 페이지에서 전환의 패리티를 학습하려면 전환의 정확한 위치를 학습해야 하며 Δ(log(k)) 쿼리가 필요합니다.쿼리 모음은 전환 지점을 간격으로 제한하며, 길이가 1보다 긴 간격은 양쪽 패리티를 모두 가집니다.이 페이지에서 전환을 위한 가장 효율적인 검색은 이진 검색입니다.

가장 미묘하고 중요한 점:특정 페이지 내에서 전환의 패리티를 결정하는 두 가지 방법이 있습니다.해당 페이지에서 충분히 쿼리하여 전환을 찾을 수도 있고, 이전 페이지와 이후 페이지 모두에서 동일한 패리티를 찾을 경우 패리티를 추론할 수도 있습니다.이 일에서 벗어날 방법은 없어요.쿼리 집합은 각 페이지의 전환 지점을 특정 간격으로 제한합니다.패리티에 대한 유일한 제한은 길이가 1인 구간에서 제공됩니다.그렇지 않으면 전환점이 자유롭게 움직여서 일관된 패리티를 가질 수 있습니다.

적수법에서는 행운의 스트라이크가 없습니다.예를 들어, 일부 페이지의 첫 번째 쿼리가 중간이 아닌 한쪽 끝을 향하고 있다고 가정합니다.상대방이 대답을 약속하지 않았기 때문에, 그는 자유롭게 전환을 보류할 수 있습니다.

결과적으로 Δ(log(k)) 페이지에서 패리티를 직접 조사해야 하며, 이러한 각 하위 문제에 대한 작업도 Δ(log(k))입니다.

무작위로 선택하는 것이 적대적인 선택을 하는 것보다 훨씬 나은 것은 아닙니다.수학은 더 복잡합니다. 왜냐하면 이제 여러분은 엄격하게 예를 알고 있거나 아니요를 알지 못하는 것보다 부분적인 통계 정보를 얻을 수 있기 때문입니다.하지만 별 차이가 없습니다.예를 들어, 각 페이지의 길이 k^2를 지정하면 각 페이지의 첫 번째 로그(k) 쿼리는 해당 페이지의 패리티에 대해 거의 아무것도 알려주지 않습니다.상대는 처음에 무작위로 선택할 수 있고 여전히 작동합니다.

배열의 중앙에서 시작하여 중앙의 값과 다른 값에 도달할 때까지 뒤로 이동합니다.경계 위의 숫자가 홀수 또는 짝수 색인에 있는지 확인합니다.홀수일 경우 홀수 횟수가 왼쪽에 있으므로 처음과 찾은 경계 사이에서 검색을 반복합니다.짝수인 경우 홀수 횟수가 배열에서 나중에 발생해야 하므로 오른쪽 절반에서 검색을 반복합니다.

위에서 설명한 바와 같이, 이것은 로그 성분과 선형 성분을 모두 가지고 있습니다.전체를 로그로 유지하려면 배열을 뒤로 이동하여 다른 값으로 이동하는 대신 이진 검색을 사용해야 합니다.그러나 동일한 숫자의 반복을 많이 기대하지 않는 한 이진 검색은 가치가 없을 수 있습니다.

log(N/C)*log(K)에서 작동하는 알고리즘이 있습니다. 여기서 K는 최대 동일 값 범위의 길이이고 C는 검색 중인 범위의 길이입니다.

이전에 게시된 대부분의 알고리즘과 다른 점은 모든 동일한 값 범위가 짧은 경우를 활용한다는 것입니다.전체 배열을 이진 검색하는 것이 아니라 먼저 1, 2, 4, 8, ...(로그(K) 반복) 단계를 건너뛰어 대략적인 추정치를 빠르게 찾은 다음 결과 범위(로그(K)를 다시 이진 검색하여 경계를 찾습니다.

알고리즘은 다음과 같습니다(C#로 작성됨).

// Finds the start of the range of equal numbers containing the index "index", 
// which is assumed to be inside the array
// 
// Complexity is O(log(K)) with K being the length of range
static int findRangeStart (int[] arr, int index)
{
    int candidate = index;
    int value = arr[index];
    int step = 1;

    // find the boundary for binary search:
    while(candidate>=0 && arr[candidate] == value)
    {
        candidate -= step;
        step *= 2;
    }

    // binary search:
    int a = Math.Max(0,candidate);
    int b = candidate+step/2;
    while(a+1!=b)
    {
        int c = (a+b)/2;
        if(arr[c] == value)
            b = c;
        else
            a = c;
    }
    return b;
}

// Finds the index after the only "odd" range of equal numbers in the array.
// The result should be in the range (start; end]
// The "end" is considered to always be the end of some equal number range.
static int search(int[] arr, int start, int end)
{
    if(arr[start] == arr[end-1])
        return end;

    int middle = (start+end)/2;

    int rangeStart = findRangeStart(arr,middle);

    if((rangeStart & 1) == 0)
        return search(arr, middle, end);
    return search(arr, start, rangeStart);
}

// Finds the index after the only "odd" range of equal numbers in the array
static int search(int[] arr)
{
    return search(arr, 0, arr.Length);
}

가운데 요소를 선택합니다.이진 검색을 사용하여 처음 및 마지막 항목을 찾습니다.O(log(n)) 홀수일 경우 e를 반환합니다.그렇지 않으면 요소 수가 홀수인 쪽으로 다시 이동합니다. [...]ee [...]

런타임은 log(n) + log(n/2) + log(n/4)... = O(log(n)^2)입니다.

아, 답이 있네요.

이진 검색을 수행하고 각 값을 검색할 때 동일한 값을 가진 첫 번째 항목을 찾을 때까지 뒤로 이동합니다.지수가 짝수일 경우 홀수 앞에 있으므로 오른쪽으로 이동합니다.
배열 인덱스가 홀수이면 홀수 공 다음에 있으므로 왼쪽으로 이동합니다.

의사 코드에서 (이것은 일반적인 생각이지, 테스트된 것이 아닙니다...):

    private static int FindOddBall(int[] ary)
    {
        int l = 0,
            r = ary.Length - 1;
        int n = (l+r)/2;
        while (r > l+2)
        {
            n = (l + r) / 2;
            while (ary[n] == ary[n-1])
                n = FindBreakIndex(ary, l, n);
            if (n % 2 == 0) // even index we are on or to the left of the oddball 
                l = n;
            else            // odd index we are to the right of the oddball
                r = n-1;
        }
        return ary[l];
    }
    private static int FindBreakIndex(int[] ary, int l, int n)
    {
        var t = ary[n];
        var r = n;
        while(ary[n] != t || ary[n] == ary[n-1])
            if(ary[n] == t)
            {
                r = n;
                n = (l + r)/2;
            }
            else
            {
                l = n;
                n = (l + r)/2;
            }
        return n;
    }

다음 알고리즘을 사용할 수 있습니다.

int GetSpecialOne(int[] array, int length)
{
   int specialOne = array[0];

   for(int i=1; i < length; i++)
   {
      specialOne ^= array[i];
   }
   return specialOne;
}

여기 http://www.technicalinterviewquestions.net 에서 찾을 수 있는 유사한 질문의 도움으로 해결되었습니다.

우리는 배열 내부의 길이 분포와 배열 전체에 대한 정보를 가지고 있지 않습니다, 그렇죠?

따라서 배열 길이는 1, 11, 101, 1001 등일 수 있으며, 적어도 1은 상한이 없을 수 있으며, 1, 11, 101:1, 1 ~ 6, 1 ~ 51 요소 등의 총 크기에 대해 (길이-1)/2 + 1개 이상의 요소 유형('숫자')을 포함해야 합니다.

가능한 모든 크기의 동일한 확률을 가정해 볼까요?이렇게 하면 4 사이즈의 서브 어레이가 중간 길이가 됩니다. 그렇지 않나요?

크기 5의 배열은 1, 2 또는 3개의 하위 목록으로 나눌 수 있습니다.

명백해 보이는 것은 우리가 세부적으로 살펴보면 그렇게 명백하지 않습니다.

크기가 5인 배열은 하나의 하위 목록으로 '분할'할 수 있으며, 이를 '분할'이라고 부르는 논쟁의 여지가 있습니다.5가지 요소(aaaa)의 목록일 뿐입니다.혼동을 방지하기 위해 목록 내의 요소를 숫자(a,b,c,...)가 아닌 순서가 지정된 문자로 가정합니다.

두 개의 하위 목록으로 나누면 (1, 4), (2, 3), (3, 2), (4, 1)일 수 있습니다. (abbbb, aaabb, aaabb, aaabb).

이제 이전에 제기된 주장을 다시 살펴보겠습니다.'division'(5)을 두 개의 하위 목록으로 나눈 4개의 분할과 동일한 확률로 가정해야 합니까?아니면 그것들을 함께 섞고 모든 파티션이 균등하게 가능하다고 가정할까요? (1/5)

아니면 우리가 서브리스트의 길이에 대한 확률을 모른 채 솔루션을 계산할 수 있습니까?

단서는 당신이 로그(n)를 찾고 있다는 것입니다.그것은 n보다 작습니다.

한 번에 하나씩 전체 어레이를 통과하는 것?그건 n입니다.그건 안 될 거예요.

배열의 처음 두 인덱스(0과 1)는 동일한 숫자여야 합니다.배열의 홀수가 그 뒤에 있으면 50과 51도 마찬가지입니다.

따라서 배열에서 중간 요소를 찾아 바로 뒤의 요소와 비교합니다.잘못된 인덱스에서 숫자의 변화가 발생하면 배열의 홀수가 앞에 있고 그렇지 않으면 다음에 있다는 것을 알 수 있습니다.한 세트의 비교를 통해 대상이 어느 쪽에 있는지 파악합니다.

거기서 계속 가세요.

해시 테이블 사용

For each element E in the input set
    if E is set in the hash table
         increment it's value
    else        
         set E in the hash table and initialize it to 0

For each key K in hash table
    if K % 2 = 1
        return K

이 알고리즘은 2n이므로 O(n)에 속합니다.

사용해 보십시오.

int getOddOccurrence(int ar[], int ar_size)
{
     int i;
     int xor = 0; 
     for (i=0; i < ar_size; i++)     
        xor = xor ^ ar[i];

     return res;
}

XOR는 1^1=0이지만 1^1^1=1인 XOR를 사용할 때마다 취소되므로 모든 쌍은 홀수를 제외하고 취소해야 합니다.

인덱싱이 0에서 시작된다고 가정합니다.x[i] != x[i+1]과 같은 최소 짝수를 이진 검색합니다. 정답은 x[i]입니다.

편집: 대중의 요구로 인해, 여기 코드가 있습니다.

int f(int *x, int min, int max) {
  int size = max;
  min /= 2;
  max /= 2;
  while (min < max) {
    int i = (min + max)/2;
    if (i==0 || x[2*i-1] == x[2*i])
      min = i+1;
    else
      max = i-1;
  }
  if (2*max == size || x[2*max] != x[2*max+1])
    return x[2*max];
  return x[2*min];
}

언급URL : https://stackoverflow.com/questions/3181071/how-can-i-find-a-number-which-occurs-an-odd-number-of-times-in-a-sorted-array-in