Алгоритм для нахождения двух повторных чисел в массиве, без сортировки

Существует O (n) решение , если Вы знаете, каков возможный домен входа. Например, если Ваш входной массив содержит числа между от 0 до 100, рассмотрите следующий код.

bool flags[100];
for(int i = 0; i < 100; i++)
    flags[i] = false;

for(int i = 0; i < input_size; i++)
    if(flags[input_array[i]])
         return input_array[i];
    else       
        flags[input_array[i]] = true;

, Конечно, существует дополнительная память, но это является самым быстрым.

Как насчет этого:

for (i=0; i<n-1; i++) {
  for (j=i+1; j<n; j++) {
    if (a[i] == a[j]) {
        printf("%d appears more than once\n",a[i]);
        break;
    }
  }
}

Уверенный это не является самым быстрым, но это просто и легко для понимания и не требует никакой дополнительной памяти. Если n является небольшим числом как 9, или 100, то это может быть "лучшим". (т.е. "Лучше всего" мог означать разные вещи: самый быстрый для выполнения, самый маленький объем потребляемой памяти, большая часть удобной в сопровождении, наименьшего количества стоимости для разработки и т.д.)

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

в psuedocode это в основном было бы (сделанный этот путь, таким образом, я только даю Вам ответ):

for each number in the list
   if number not already in unique numbers list
      add it to the unique numbers list
   else
      return that number as it is a duplicate
   end if
end for each

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

Вот реализация в Python ответ @eugensk00 (одно из его изменений), который не использует арифметику в остаточных классах. Это однопроходное алгоритм, O (журнал (n)) в пространстве . Если фиксированная ширина (например, 32-разрядный) целые числа используются затем, это, требует только двух чисел фиксированной ширины (например, для 32-разрядного: одно 64-разрядное число и одно 128-разрядное число). Это может обработать произвольные большие целочисленные последовательности (это читает одно целое число за один раз поэтому, целая последовательность не требует, чтобы быть в памяти).

def two_repeated(iterable):
    s1, s2 = 0, 0
    for i, j in enumerate(iterable):
        s1 += j - i     # number_of_digits(s1) ~ 2 * number_of_digits(i)
        s2 += j*j - i*i # number_of_digits(s2) ~ 4 * number_of_digits(i) 
    s1 += (i - 1) + i
    s2 += (i - 1)**2 + i**2

    p = (s1 - int((2*s2 - s1**2)**.5)) // 2 
    # `Decimal().sqrt()` could replace `int()**.5` for really large integers
    # or any function to compute integer square root
    return p, s1 - p

Пример:

>>> two_repeated([2, 3, 6, 1, 5, 4, 0, 3, 5])
(3, 5)

А больше подробной версии вышеупомянутого кода следует с объяснением:

def two_repeated_seq(arr):
    """Return the only two duplicates from `arr`.

    >>> two_repeated_seq([2, 3, 6, 1, 5, 4, 0, 3, 5])
    (3, 5)
    """
    n = len(arr)
    assert all(0 <= i < n - 2 for i in arr) # all in range [0, n-2)
    assert len(set(arr)) == (n - 2) # number of unique items

    s1 = (n-2) + (n-1)       # s1 and s2 have ~ 2*(k+1) and 4*(k+1) digits  
    s2 = (n-2)**2 + (n-1)**2 # where k is a number of digits in `max(arr)`
    for i, j in enumerate(arr):
        s1 += j - i     
        s2 += j*j - i*i

    """
    s1 = (n-2) + (n-1) + sum(arr) - sum(range(n))
       = sum(arr) - sum(range(n-2))
       = sum(range(n-2)) + p + q - sum(range(n-2))
       = p + q
    """
    assert s1 == (sum(arr) - sum(range(n-2)))

    """
    s2 = (n-2)**2 + (n-1)**2 + sum(i*i for i in arr) - sum(i*i for i in range(n))
       = sum(i*i for i in arr) - sum(i*i for i in range(n-2))
       = p*p + q*q
    """
    assert s2 == (sum(i*i for i in arr) - sum(i*i for i in range(n-2)))

    """
    s1 = p+q
    -> s1**2 = (p+q)**2
    -> s1**2 = p*p + 2*p*q + q*q
    -> s1**2 - (p*p + q*q) = 2*p*q
    s2 = p*p + q*q
    -> p*q = (s1**2 - s2)/2

    Let C = p*q = (s1**2 - s2)/2 and B = p+q = s1 then from Viete theorem follows
    that p and q are roots of x**2 - B*x + C = 0
    -> p = (B + sqrtD) / 2
    -> q = (B - sqrtD) / 2
    where sqrtD = sqrt(B**2 - 4*C)

    -> p = (s1 + sqrt(2*s2 - s1**2))/2
    """
    sqrtD = (2*s2 - s1**2)**.5
    assert int(sqrtD)**2 == (2*s2 - s1**2) # perfect square
    sqrtD = int(sqrtD)
    assert (s1 - sqrtD) % 2 == 0 # even
    p = (s1 - sqrtD) // 2
    q = s1 - p
    assert q == ((s1 + sqrtD) // 2)
    assert sqrtD == (q - p)
    return p, q

ПРИМЕЧАНИЕ: вычисление целочисленного квадратного корня числа (~ N ** 4) делает вышеупомянутый алгоритм нелинейным.

Сортировка массива, казалось бы, была бы лучшим решением. Простой вид затем сделал бы поиск тривиальным и займет намного меньше времени/пространства.

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

int count [10];

for (int i = 0; i < arraylen; i++) {
    count[array[i]]++;
}

Затем просто ищут Ваш массив любые числа, больше, чем 1. Это - объекты с дубликатами. Только требует одной передачи через исходный массив и одной передачи через массив количества.

Некоторые ответы на вопрос: Алгоритм, чтобы определить, содержит ли массив n†¦ n+m? содержат как подпроблема решения, которые можно принять для цели.

, Например, вот соответствующая часть от мой ответ :

bool has_duplicates(int* a, int m, int n)
{
  /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')

      Whether a[] array has duplicates.

      precondition: all values are in [n, n+m) range.

      feature: It marks visited items using a sign bit.
  */
  assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
  for (int *p = a; p != &a[m]; ++p) {
    *p -= (n - 1); // [n, n+m) -> [1, m+1)
    assert(*p > 0);
  }

  // determine: are there duplicates
  bool has_dups = false;
  for (int i = 0; i < m; ++i) {
    const int j = abs(a[i]) - 1;
    assert(j >= 0);
    assert(j < m);
    if (a[j] > 0)
      a[j] *= -1; // mark
    else { // already seen
      has_dups = true;
      break;
    }
  }

  // restore the array
  for (int *p = a; p != &a[m]; ++p) {
    if (*p < 0) 
      *p *= -1; // unmark
    // [1, m+1) -> [n, n+m)
    *p += (n - 1);        
  }

  return has_dups; 
}

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

Это работает на размеры массива [до 111] (в 64-разрядных системах, которые это 9223372036854775807).

Проверьте эту старую, но хорошую статью о теме:

• Открытие Повторные Элементы (PDF)

Вы смогли использовать в своих интересах то, что сумма (массив) = (n-2) * (n-3)/2 + два недостающих числа.

Редактирование: Как другие отметили, объединились с суммой квадратов, можно использовать это, я был просто немного медленным в понимании ее.

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

Вы знаете, что Ваш Массив содержит каждое число от 0 до n-3 и двух повторяющихся (p & q). Для простоты, позволяет, игнорируют с 0 случаями на данный момент.

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

1 + 2 + ... + n-3 + p + q = p + q + (n-3)(n-2)/2

Поэтому, если Вы substract (n-3) (n-2)/2 от суммы целого массива, Вы добираетесь

sum(Array) - (n-3)(n-2)/2 = x = p + q

Теперь, делают то же для продукта:

1 * 2 * ... * n - 3 * p * q = (n - 3)! * p * q

prod(Array) / (n - 3)! = y = p * q

Ваш теперь получил эти условия:

x = p + q

y = p * q

=> y(p + q) = x(p * q)

при преобразовании этого термина необходимо смочь вычислить p и q

Хорошо, кажется, что я просто не могу дать ему отдых :)

Простое решение

int A[N] = {...};

int signed_1(n) { return n%2<1 ? +n : -n;  } // 0,-1,+2,-3,+4,-5,+6,-7,...
int signed_2(n) { return n%4<2 ? +n : -n;  } // 0,+1,-2,-3,+4,+5,-6,-7,...

long S1 = 0;  // or int64, or long long, or some user-defined class
long S2 = 0;  // so that it has enough bits to contain sum without overflow

for (int i=0; i<N-2; ++i)
{
   S1 += signed_1(A[i]) - signed_1(i);
   S2 += signed_2(A[i]) - signed_2(i);
} 

for (int i=N-2; i<N; ++i)
{
   S1 += signed_1(A[i]);
   S2 += signed_2(A[i]);
} 

S1 = abs(S1);
S2 = abs(S2);

assert(S1 != S2);  // this algorithm fails in this case

p = (S1+S2)/2;
q = abs(S1-S2)/2;

, Одна сумма (S1 или S2) содержит p и q с тем же знаком, другой суммой - с противоположными знаками, все другие участники устраняются.
S1 и S2 должны иметь достаточно битов для размещения сумм, алгоритм не обозначает переполнение из-за брюшного пресса ().

, если брюшной пресс (S1) == брюшной пресс (S2) затем сбои алгоритма, хотя это значение все еще будет различием между p и q (т.е. брюшной пресс (p - q) == брюшной пресс (S1)).

Предыдущее решение

я сомневаюсь, что кто-то будет когда-либо встречаться с такой проблемой в поле ;)
, и я предполагаю, я знаю ожидание учителя:

Позволяет, берут массив {0,1,2..., n-2, n-1},
, учитывая можно быть произведен путем замены последних двух элементов n-2 и n-1 с неизвестным p и q (меньше порядка)

так, сумма элементов будет (n-1) n/2 + p + q - (n-2) - (n-1)
сумма квадратов (n-1) n (2n-1)/6 + p^2 + q^2 - (n-2) ^2 - (n-1) ^2

, которым остается Простая математика:

  (1)  p+q = S1  
  (2)  p^2+q^2 = S2

, Конечно, Вы не решите его, как математические классы учат для решения квадратных уравнений.

Первый, вычислите, все по модулю 2^32, то есть, допускает переполнение.
Затем пары проверки {p, q}: {0, S1}, {1, S1-1}... против выражения (2) для нахождения кандидатов (могли бы быть больше чем 2 из-за модуля и придающий квадратную форму)
, И наконец проверьте найденных кандидатов, если они действительно присутствуют в массиве дважды.

suppose array is

a[0], a[1], a[2] ..... a[n-1]

sumA = a[0] + a[1] +....+a[n-1]
sumASquare = a[0]*a[0] + a[1]*a[1] + a[2]*a[2] + .... + a[n]*a[n]

sumFirstN = (N*(N+1))/2 where N=n-3 so
sumFirstN = (n-3)(n-2)/2

similarly

sumFirstNSquare = N*(N+1)*(2*N+1)/6 = (n-3)(n-2)(2n-5)/6

Suppose repeated elements are = X and Y

so X + Y = sumA - sumFirstN;
X*X + Y*Y = sumASquare - sumFirstNSquare;

So on solving this quadratic we can get value of X and Y.
Time Complexity = O(n)
space complexity = O(1)

for(i=1;i<=n;i++) {
  if(!(arr[i] ^ arr[i+1]))
        printf("Found Repeated number %5d",arr[i]);
}

Почему мы должны попробовать заниматься математикой (особенно решать квадратные уравнения), это дорогостоящая операция. Лучший способ решить эту проблему - создать растровое изображение размером (n-3) бит, то есть (n -3) +7/8 байтов. Лучше сделать calloc для этой памяти, чтобы каждый бит был инициализирован равным 0. Затем просмотрите список и установите конкретный бит в 1 при обнаружении, если бит уже установлен в 1 для этого «нет», то это повторяется «нет». Это может быть расширено, чтобы узнать, есть ли в массиве какие-то пропущенные «нет» или нет. Это решение имеет временную сложность O (n)