Как я могу найти число, которое встречается нечетное количество раз в массиве SORTED за O (n) раз?

Question

У меня есть вопрос, и я пытался обдумать его снова и снова ... но не получил ничего, поэтому разместил вопрос здесь. Может быть, я мог бы получить какую-то точку зрения других, чтобы попытаться заставить это работать ...

Вопрос в том, что нам дан массив SORTED, который состоит из набора значений, встречающихся ДАЖЕ раз, кроме одного, которое встречается ODD несколько раз. Нам нужно найти решение в log n раз.

Легко найти решение за время O (n), но это выглядит довольно сложно для выполнения за время log n.

Answer 1

Теорема : Каждый детерминистический алгоритм для этой задачи исследует Ω (log ² n) областей памяти в худшем случаеcase.

Доказательство (полностью переписано в более формальном стиле):

Пусть k> 0 будет нечетным целым числом и пусть n = k ² .Мы описываем противника, который заставляет (log ₂ (k + 1)) ² = Ω (log ² n) зондов.

Weназвать максимальные подпоследовательности идентичных элементов групп .Возможные входы противника состоят из k длины-k сегментов x ₁ x ₂ … x _k .Для каждого сегмента x _j существует целое число b _j ∈ [0, k], такое что x _j состоит из b _j копии j - 1, за которыми следуют k - b _j копии j.Каждая группа перекрывает не более двух сегментов, а каждый сегмент перекрывает не более двух групп.

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) однозначно определяется сегментом x _j .

Доказательство : Это сразу после ((j - 1) k + b _j ) ^th ячейка памяти и x _j однозначно определяет b _j .//

Мы говорим, что алгоритм наблюдал границу группы j ^th в случае, если результаты его исследований x _j однозначно определяютх _J .По соглашению, начало и конец ввода всегда соблюдаются.Алгоритм может однозначно определить местоположение границы группы, не наблюдая ее.

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

При заданном только 0 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 , он выбирает значение, которое оставляет как минимум половину оставшихся возможностей (относительно наблюдения).В противном случае он выбирает так, чтобы сохранить как минимум половину групп в соответствующем интервале, и фиксирует значения для остальных.

Таким образом, злоумышленник заставляет алгоритм наблюдать как минимум log ₂ (k + 1) групповых границ, и при наблюдении j ^th групповой границы алгоритм вынужден создавать как минимум log ₂ (k + 1) зондов.

---

Расширения:

Этот результат прямо распространяется на рандомизированных алгоритмов путем рандомизации ввода, заменяя «в лучшем случае пополам» (с точки зрения алгоритма)зрения) с "в лучшем случае вдвое меньшим в ожидании" и применением стандартных неравенств концентрации.

Это также распространяется на случай, когда ни одна группа не может быть больше, чем s копий;в этом случае нижняя граница составляет Ом (log n log s) .

Answer 2

Сортированный массив предлагает бинарный поиск.Мы должны пересмотреть равенство и сравнение.Простое равенство означает нечетное количество элементов.Мы можем сделать сравнение, наблюдая за индексом первого или последнего элемента группы.Первым элементом будет четный индекс (на основе 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)²)

Answer 3

Посмотрите на средний элемент массива. С помощью пары соответствующих двоичных поисков вы можете найти первое и последнее появление в массиве. Например, если средний элемент 'a', вам нужно найти i и j, как показано ниже:

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

Является ли j - i четным числом? Вы сделали! В противном случае (и это ключ здесь), вопрос, который нужно задать , является ли я четным или нечетным числом ? Вы видите, что подразумевает этот кусок знания? Тогда остальное легко.

Answer 4

Этот ответ в поддержку ответа, опубликованного "throwawayacct". Он заслуживает награды. Я потратил некоторое время на этот вопрос, и я полностью убежден, что его доказательство верно, что вам нужно Ω (log (n) ^ 2) запросов, чтобы найти число, которое встречается нечетное количество раз. Я убежден, потому что в итоге я воссоздал точно такой же аргумент, только просматривая его решение.

В этом решении злоумышленник создает входные данные, которые усложняют работу алгоритма, а также упрощают анализатор для человека. Вход состоит из k страниц, каждая из которых имеет k записей. Общее количество записей равно n = k ^ 2, и важно, чтобы O (log (k)) = O (log (n)) и Ω (log (k)) = Ω (log (n)). Чтобы сделать ввод, противник создает строку длиной k вида 00 ... 011 ... 1 с переходом в произвольную позицию. Затем каждый символ в строке раскрывается в страницу длиной k в форме aa ... abb ... b, где на i-й странице a = i и b = i + 1. Переход на каждой странице также находится в произвольной позиции, за исключением того, что четность согласуется с символом, с которого страница была расширена.

Важно понимать «метод противника» анализа наихудшего случая алгоритма. Злоумышленник отвечает на вопросы о входе алгоритма, не принимая будущих ответов. Ответы должны быть непротиворечивыми, и игра заканчивается, когда злоумышленник прижат достаточно, чтобы алгоритм смог прийти к выводу.

На этом фоне приведены некоторые наблюдения:

1) Если вы хотите узнать четность перехода на странице, выполняя запросы на этой странице, вам нужно узнать точную позицию перехода, и вам нужно Ω (log (k)) запросов. Любая коллекция запросов ограничивает точку перехода интервалом, а любой интервал длиной более 1 имеет обе четности. Наиболее эффективным поиском перехода на этой странице является бинарный поиск.

2) Самый тонкий и самый важный момент: Существует два способа определения четности перехода внутри конкретной страницы. Вы можете сделать достаточно запросов на этой странице, чтобы найти переход, или вы можете сделать вывод о четности, если вы найдете одинаковый паритет как на более ранней, так и на более поздней странице. От этого никуда не уйдешь. Любой набор запросов ограничивает точку перехода на каждой странице некоторым интервалом. Единственное ограничение на четность исходит из интервалов длины 1. В противном случае точки перехода могут свободно колебаться, чтобы иметь любые согласованные четности.

3) В методе противника нет счастливых ударов. Например, предположим, что ваш первый запрос на некоторой странице направлен к одному концу, а не к середине. Поскольку противник не взял на себя ответ, он может поставить переход на длинную сторону.

4) Конечным результатом является то, что вы вынуждены непосредственно проверять четности на страницах Ω (log (k)), и работа для каждой из этих подзадач также является Ω (log (k)).

5) При случайном выборе дела обстоят не намного лучше, чем при состязательном выборе. Математика более сложна, потому что теперь вы можете получить частичную статистическую информацию, а не строгое: да, вы знаете соотношение или нет, вы его не знаете. Но это мало что меняет. Например, вы можете указать длину каждой страницы k ^ 2, чтобы с высокой вероятностью первые запросы log (k) на каждой странице почти ничего не говорили о четности на этой странице. Противник может сделать случайный выбор в начале, и он все еще работает.

Answer 5

Начните с середины массива и идите назад, пока не получите значение, отличное от значения в центре.Проверьте, имеет ли число выше этой границы нечетный или четный индекс.Если это нечетное число, то число, встречающееся нечетное число раз, находится слева, поэтому повторите поиск между началом и найденной границей.Если оно четное, то число, встречающееся нечетное число раз, должно быть позже в массиве, поэтому повторите поиск в правой половине.

Как указано, это имеет как логарифмический, так и линейный компонент.Если вы хотите сохранить все это логарифмическим, вместо того, чтобы просто идти назад по массиву к другому значению, вы хотите использовать вместо этого бинарный поиск.Если вы не ожидаете много повторений одних и тех же чисел, бинарный поиск может быть не оправдан.

Answer 6

У меня есть алгоритм, который работает в log (N / C) * log (K), где K - длина максимального диапазона того же значения, а C - длина искомого диапазона.

Основным отличием этого алгоритма от большинства опубликованных ранее является то, что он использует тот случай, когда все диапазоны одинаковых значений короткие.Он находит границы не путем бинарного поиска по всему массиву, но сначала быстро находит приблизительную оценку, возвращаясь назад на 1, 2, 4, 8, ... (log (K) итераций) шагов, а затем выполняет бинарный поискрезультирующий диапазон (снова log (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);
}

Answer 7

Возьмите средний элемент e.Используйте бинарный поиск, чтобы найти первое и последнее вхождение.O (log (n)) Если это нечетно, верните e.В противном случае вернитесь на сторону, имеющую нечетное число элементов [....] eeee [....]

Время выполнения будет log (n) + log (n / 2) + log (n/ 4) .... = O (log (n) ^ 2).

Answer 8

Вы можете использовать этот алгоритм:

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

Answer 9

аааа.Есть ответ.

Выполните бинарный поиск и, по мере поиска, для каждого значения перемещайтесь назад, пока не найдете первую запись с тем же значением.Если его индекс четный, он находится перед нечетным, поэтому переместитесь вправо.
Если его индекс массива нечетный, то после нечетного, поэтому переместитесь влево.

В псевдокоде (этоэто общая идея, не проверенная ...):

    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;
    }

Answer 10

Попробуйте это:

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 будет отменять каждый раз, когда вы XOR с тем же номером, поэтому 1 ^ 1 = 0, но 1 ^ 1 ^ 1 = 1, поэтому каждая пара должна отменять, оставляя нечетное число вне.