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

Question

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

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

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

Answer 1

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

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)

Answer 2

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

Пошагово по всему массиву, по одному? Это п. Это не сработает.

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

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

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

Answer 3

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

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;

    }
}

Answer 4

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

Answer 5

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

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

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

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

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

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

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

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

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