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

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

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

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

Мы называем максимальные подпоследовательности одинаковых элементов группами. Возможные входные данные злоумышленника состоят из 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^й границы группы (1 ≤ j ≤ k) однозначно определяется отрезком x_j.

Доказательство: сразу после ((j - 1) k + b_j)^th ячейки памяти и x_{j однозначно определяет bj. //}

Мы говорим, что алгоритм обнаружил границу группы j^th, если результаты его проверки x_j однозначно определяют x_{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^й границы группы алгоритм вынужден сделать не менее log₂ (k + 1) проб.

Расширения:

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

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

Отсортированный массив предполагает бинарный поиск. Мы должны дать новое определение равенству и сравнению. Равенство простое означает нечетное количество элементов. Мы можем выполнить сравнение, наблюдая за индексом первого или последнего элемента группы. Первый элемент будет иметь четный индекс (начиная с 0) перед нечетной группой и нечетный индекс после нечетной группы. Мы можем найти первый и последний элементы группы с помощью бинарного поиска. Общая стоимость составляет O((log N)²).

ДОКАЗАТЕЛЬСТВО O((log 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 четное число? Вы сделали! В противном случае (и это ключевой момент здесь) следует задать вопрос является ли я четным или нечетным числом? Вы понимаете, что означает это знание? Тогда остальное легко.

Этот ответ поддерживает ответ, опубликованный «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) на каждой странице почти ничего не сообщат вам о четности на этой странице. Противник может сделать случайный выбор в начале, и это все еще работает.

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

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

У меня есть алгоритм, который работает в формате 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);
}

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

Время выполнения будет 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 тип элементов («число») до (длина-1)/2 + 1 элементов, для суммарных размеров 1, 11, 101: 1, от 1 до 6, от 1 до 51 элемента и так далее.

Должны ли мы принять все возможные размеры с равной вероятностью? Это привело бы к средней длине подмассивов размера / 4, не так ли?

Массив размера 5 можно разделить на 1, 2 или 3 подсписка.

То, что кажется очевидным, не так уж и очевидно, если вдаваться в подробности.

Массив размера 5 может быть "разделен" на один подсписок только одним способом, с спорным правом называть это "делением". Это просто список из 5 элементов (ааааа). Чтобы избежать путаницы, давайте предположим, что элементы внутри списка являются упорядоченными символами, а не числами (a,b,c,...).

Разделенные на два подсписка, они могут быть (1, 4), (2, 3), (3, 2), (4, 1). (аббб, ааббб, ааабб, ааааб).

Теперь давайте вернемся к заявлению, сделанному ранее: следует ли предположить, что «деление» (5) имеет ту же вероятность, что и эти 4 деления на 2 подсписка? Или мы смешаем их вместе и будем считать каждое деление равновероятным (1/5)?

Или мы можем вычислить решение, не зная вероятности длины подсписков?

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

Вы можете создать кумулятивный массив и подсчитать, сколько раз встречается каждое число, а затем в кумулятивном массиве найти нечетный элемент. Пример:

int a[]=new int[]{2,3,4,2,3,1,4,5,6,5,6,7,1};
int b[]=new int[1000];
for (int i=0;i<b.length;i++) {
    b[i]=0;
}
for (Int i=0;i<a.length;i++) {
    b[a[i]]++;
}
for (int i=0;i<b.length;i++) {
    if ( b[i]!=0) {
        if (b[i] %2==0) {
          system.out.println(i);  break;

    }
}

Предположим, что индексация начинается с 0. Двоичный поиск наименьшего четного i такого, что x[i] != x[i+1]; ваш ответ х[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];
}