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

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

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

У нас нет никакой информации о распределении длин внутри массива и массива в целом, верно?

Значит, длина массива может быть 1, 11, 101, 1001 или что-то еще, 1, по крайней мере, без верхней границы, и должен содержать по крайней мере 1 тип элементов ("число") до (length-1)/2 + 1 элементов, для общих размеров 1, 11, 101: 1, от 1 до 6, от 1 до 51 элемента и так далее.

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

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

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

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

Если разделить список на два подсписка, то они могут быть такими: (1, 4), (2, 3), (3, 2), (4, 1). (abbbb, aabbb, aaabb, aaaab).

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

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

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

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

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

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

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;

    }
}

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

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

Теорема: Каждый детерминированный алгоритм для этой задачи в худшем случае зондирует Ω(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 однозначно определяет b_j. //

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

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

Имея только 0 0 ?, алгоритм не может точно сказать, является ли ? 0 или 1. В контексте, однако, ? должна быть 1, так как в противном случае было бы три нечетные группы, и граница группы в X может быть выведена. Эти выводы могут быть проблематичными для противника, но оказывается, что они могут быть сделаны только после того, как рассматриваемая граница группы станет "неактуальной".

Claim: В любой момент выполнения алгоритма рассмотрим набор наблюдаемых им групповых границ. Ровно одна последовательная пара находится на нечетном расстоянии, и между ними лежит нечетная группа.

Proof: Все остальные последовательные пары ограничивают только четные группы. //

Определим подпоследовательность нечетной длины, ограниченную специальной последовательной парой, как соответствующую подпоследовательность.

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

Proof: Без потери общности предположим, что каждая область памяти, не входящая в соответствующую подпоследовательность, была прозондирована и что каждый сегмент, содержащийся в соответствующей подпоследовательности, имеет ровно одну область, которая не была прозондирована. Предположим, что граница j^-й группы (назовем ее B) лежит во внутренней части соответствующей подпоследовательности. По гипотезе, зондирование x_j определяет местоположение B до двух последовательных возможностей. Мы называем одну из них, находящуюся на нечетном расстоянии от левой наблюдаемой границы odd-left, а другую odd-right. Для обеих возможностей мы работаем слева направо и фиксируем расположение каждой оставшейся внутренней границы группы так, чтобы группа слева от нее была четной. (Мы можем это сделать, потому что у каждой из них также есть две последовательные возможности). Если 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^-я граница была наблюдаема, он выбирает значение, которое оставляет по крайней мере половину оставшихся возможностей (в отношении наблюдения). В противном случае он выбирает так, чтобы по крайней мере половина групп оставалась в соответствующем интервале, и фиксирует значения для остальных.

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

Расширения:

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

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

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

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

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

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

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

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

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

Подсказка в том, что вы ищете журнал (n). Это меньше n.

Поочередно проходить через весь массив? Это п. Это не сработает.

Мы знаем, что первые два индекса в массиве (0 и 1) должны быть одинаковыми. То же самое с 50 и 51, если нечетное число в массиве после .

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

Продолжайте движение оттуда.

Этот ответ поддержал ответ, опубликованный "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, где на первой странице a=i и b=i+1. Переход на каждой странице также находится в произвольном положении, за исключением того, что четность согласуется с символом, с которого была развернута страница.

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

Исходя из этого, приведем некоторые наблюдения:

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

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

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

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

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