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

Ответ 1

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

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

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

Назовем максимальные подпоследовательности одинаковых элементов групп. Возможные входы противников состоят из k length-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 однозначно определяют 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 ^th алгоритм вынужден сделать не менее log ₂ (k + 1) зондов.

Расширения:

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

С учетом этого, вот несколько замечаний:

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

Основное отличие этого алгоритма от большинства опубликованных ранее заключается в том, что он использует преимущество, когда все диапазоны с одинаковым значением являются короткими. Он обнаруживает границы не путем двоичного поиска всего массива, а путем быстрого поиска приблизительной оценки путем повторения шагов 1, 2, 4, 8,... (log (K) итераций), а затем двоичного поиска результирующий диапазон (log (K) снова).

Алгоритм выглядит следующим образом (написан на С#):

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

Ответ 7

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

Runtime будет log (n) + log (n/2) + log (n/4).... = O (log (n) ^ 2).

Ответ 8

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

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

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

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

Ответ 9

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

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

Ответ 10

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

Таким образом, длина arraylength может быть 1, 11, 101, 1001 или что-то, 1, по крайней мере, без верхней границы и должно содержать не менее 1 типа элементов ('number') до (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) предполагается такой же, как и четыре дивизии, на 2 подсписках? Или мы будем смешивать их вместе и считать каждое разделение равномерно вероятным (1/5)?

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

Ответ 11

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

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

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

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

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

Ответ 12

Использовать хеш-таблицу

For each element E in the input set
    if E is set in the hash table
         increment it 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)

Ответ 13

Попробуйте следующее:

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, чтобы каждая пара должна отменить выход из нечетного номера.

Ответ 14

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

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;

    }
}

Ответ 15

Предположим, что начало индексирования равно 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];
}