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

Ответ 1

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

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

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

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

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

Причина этого в том, что x xor x = 0.

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

Ответ 2

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

Ответ 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;
}

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 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

Ответ 7

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

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

Ответ 8

Если вы знаете min и max целочисленной последовательности и min >= 0, создайте массив [min, max], заполненный нулями. Сканируйте данный массив, и если я произойдет, увеличьте i-ю позицию на единицу. После завершения у вас есть таблица частот во втором массиве, где позиция массива указывает на целое число.

Ответ 9

int count[2^32];
for x in input:
  count[x] = 0;  // delete this loop if you can assume ram is cleared to 0.
for x in input:
  count[x]++;
for x in input:
  if count[x] == 3:
    return x

Извините смешение языков:-) Кроме того, это действительно глупо иметь массив, который может быть проиндексирован с любым целым числом - вы можете сделать это на 64-битной системе и соответствовать требованиям.

Ответ 10

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

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

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

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

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

Ответ 11

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