Учитывая массив целых чисел, где некоторые числа повторяются 1 раз или 2 раза, но одно число повторяется 3 раза, как вы находите это?

Question

Учитывая массив целых чисел, где некоторые числа повторяются 1 раз, некоторые числа повторяются 2 раза, и только одно число повторяется 3 раза, как найти число, которое повторяется 3 раза.Использование хэша было запрещено.Сложность алгоритма должна быть O (n)

Answer 1

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

Если повторы разбросаны, то проблема становится более интересной.

Поскольку это домашнее задание, я дам вам только подсказку.

Эта проблема - двоюродная сестра того, где вам далимассив несортированных целых чисел, и все числа появляются четное число раз, кроме одного, которое появляется нечетное число раз.

Это число можно довольно легко найти в O(N), выполнив исключающее-или из всехчисла в массиве;результат - число, которое появляется нечетное число раз.

Причина, по которой это работает, заключается в том, что x xor x = 0.

Так, например, 3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7.

Answer 2

По сути, проблема состоит в том, чтобы вычислить режим массива. Это решение работает "ТОЛЬКО", если диапазон массива равен [0, n-1] . Помещение решения здесь, так как проблема не ставит пункт диапазона.

• Предположим, что 'n' - это размер массива
• Сканирование массива и отметка A [A [i]] = A [A [i]] + n -----> 1-й проход
• Разделите каждый элемент массива на 'n', т. Е. A [i] = A [i] / n ----> 2-й проход
• Ответом является элемент с максимальным значением из 2-го прохода.

Это O (n) с пробелом O (1) (но с предложением диапазона).

Мне не известен ни один алгоритм для вычисления режима в O (n), O (1) без каких-либо предложений в диапазоне.

Answer 3

Вот ответ, который предполагает, что max (A) достаточно мало, где A - входной массив:

int ValidCount(int[] a, int[] b, int i, int n) {
  int num = a[i];
  int ret = 0;
  if (b[3*num] >= 0 && b[3*num] < n && a[b[3*num]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+1] < n && a[b[3*num+1]] == num) ret++;
  if (b[3*num+1] >= 0 && b[3*num+2] < n && a[b[3*num+2]] == num) ret++;
  b[3*num+ret] = i;
  return ++ret;
}

int threerep(int[] A, int aSize) {
  int *B = malloc(sizeof(int) * 3 * max(A, aSize)); /* Problematic if max(A) is large */
  /* Note that we don't rely on B being initialized before use */
  for(int i = 0; i < aSize; i++) {
    if (ValidCount(A, B, i, aSize) == 3) return A[i];
  }
  return ERROR_NO_ANSWER;
}

Answer 4

Используйте радикальную сортировку (которая является линейной по количеству битов, необходимых для указания целых чисел), затем выполните поиск триплета.

Answer 5

Алгоритм Bugaoo выглядит аккуратно, что приведено ниже. На самом деле, мы можем обобщить его, выполнив дополнительный проход перед «1-м проходом», чтобы найти min (A) и max (A), и еще один дополнительный проход, чтобы переместить каждый элемент в A в диапазон min (A) и max (A) A [0] -мин (A). После «1-го прохода» и «2-го прохода» (обратите внимание, что мы должны изменить элементы с помощью max (A) -min (A) вместо n), мы могли бы добавить min (A) к найденному в конце дублированному числу.

По сути, проблема заключается в том, чтобы вычислить режим работы массива. Это решение работает "ТОЛЬКО", если диапазон массива равен [0, n-1]. Положить решение здесь, так как проблема не ставит пункт диапазона. Предположим, что 'n' - это размер массива. Сканируйте массив и отметьте A [A [i]] = A [A [i]] + n -----> 1-й проход. Разделите каждый элемент массива на 'n', т.е. A [i] = A [i] / n ----> 2-й проход Элемент с максимальным значением из второго прохода является ответом. Это O (n) с пробелом O (1) (но с предложением range). Я не знаю ни одного алгоритма для вычисления режима в O (n), O (1) без предложений о диапазоне.

Answer 6

Я не понимаю, о чем идет речь? используя Python 2.6 и простая функция, которая просматривает список, подсчитывает вхождения, когда находит число, встречающееся 3 раза, возвращает его.

>>> def find3(l):
    from collections import defaultdict
    d = defaultdict(int)
    for n in l:
        d[n]+=1
        if d[n] == 3:
            return n


>>> print find3([1,1,1,2,3,4,5,6,7])
1
>>> print find3([1,1,2,3,4,5,6,7,5])
None
>>> print find3([1,1,2,3,4,5,6,7,5,4,5,5])
5

Answer 7

Ну, все, о чем я могу думать, это об этом, но я уверен, что ваш профессор ищет сложное уравнение, которое решит это в 1 сканировании. Вы можете сделать это в 2 сканированиях, что составляет O (n), предполагая, что вы можете создать 2-й массив размером (от 0 до максимального числа в 1-м массиве) Сканирование один раз, найти максимальное количество в массиве. Создайте второй массив этого размера. Повторите итерацию по первому массиву снова, используя второй массив в качестве сегментов, чтобы увеличить счетчик для каждого элемента в первом массиве. Как только вы увеличиваете ведро до 3, это ваше решение. Не самый лучший, но в некоторых случаях это сработает.

Answer 8

Я представлю решение, которое в целом работает, так что одно число встречается m раз, а другие n раз.

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

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

For example, given array = [3, -4, 3, 3], m = 1 and n = 3:
Binary of 3 = 011
Binary of -4 (2s complement) = 11111111111111111111111111111100

Bit 0: 3 % 3 = 0
Bit 1: 3 % 3 = 0
Bit 2 through 32: 1 % 3 = 1
The result is -4

Answer 9

Этот алгоритм выглядит довольно неплохо .... но я не знаю, как его реализовать .. Только псевдокод .... Если что-нибудь1 хорошо попробуете в своих руках код (программирование на C), то, пожалуйста, опубликуйте его ....

Псевдокод идет здесь ... Возьмите два набора битов размера n. Мы можем использовать этот массив для подсчета до трех вхождений, т.е. если array1 [i] = 1 и array2 [i] = 1, то это означает, что у нас есть три вхождения i + 1-й элемент.

для каждого целого числа 'i' if (array2 [i] == 1) массив2 [i] = 0, массив1 [i] = 1; еще array2 [i] = 1;

для каждого элемента K в массивах if (array1 [k] && array2 [k]) возврат к;

Сложность = O (n) и пробел = 2n бит.

Answer 10

void main()
{
    int a[10]={1,5,2,8,5,9,0,5,3,7}, n, i, j, k=0;
    int p;
    printf("\n");
    for(i=0; i<10; i++)
    {
        p=1;
        for(j=i+1; j<10; j++)
        {
            if(a[i]==a[j])
                p++;
        }
        if(p==3)
        {
            printf("the no is: %d",a[i]);
            getch();
            exit(0);
        }
    }
    printf("not available\n");
    getch();
}