Алгоритм поиска двух повторяющихся чисел в массиве без сортировки

Question

Существует массив размером n (числа от 0 до n - 3), и только 2 числа повторяются. Элементы размещаются в массиве случайным образом.

например. в {2, 3, 6, 1, 5, 4, 0, 3, 5} n = 9, а повторные числа равны 3 и 5.

Как лучше всего найти повторяющиеся числа?

P.S. [Вы не должны использовать сортировку]

Answer 1

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

Answer 2

проверить это ... O (n) время и O (1) сложность пространства

 for(i=0;i< n;i++)
 xor=xor^arr[i]
 for(i=1;i<=n-3;i++)
 xor=xor^i;

Так что в данном примере вы получите xor 3 и 5

xor=xor & -xor  //Isolate the last digit

for(i = 0; i < n; i++)
{
if(arr[i] & xor)
  x = x ^ arr[i]; 
else
  y = y ^ arr[i]; 
}
for(i = 1; i <= n-3; i++)
{
if(i & xor)
  x = x ^ i; 
else
  y = y ^ i; 

}

х и у ваши ответы

Answer 3

ответ на 18 .. вы берете массив из 9, а элементы начинаются с 0 ... так что max ele будет 6 в вашем массиве. Возьмите сумму элементов от 0 до 6 и возьмите сумму элементов массива. рассчитать их разницу (скажем, г). Это р + д. Теперь возьмите XOR элементов от 0 до 6 (скажем, x1). Теперь возьмите XOR элементов массива (скажем, x2). x2 - это XOR всех элементов от 0 до 6, за исключением двух повторяющихся элементов, поскольку они взаимно уничтожают друг друга. теперь для i = от 0 до 6, для каждого элемента массива, скажите, что p - это ele a [i], так что вы можете вычислить q, вычтя этот элемент из d. сделать XOR для p и q и XOR их с помощью x2 и проверить, если x1 == x2. аналогично, выполнив все элементы, вы получите элементы, для которых это условие будет выполнено, и вы выполнили за O (n). Продолжайте кодировать!

Answer 4

Вы можете использовать простые вложенные для цикла

 int[] numArray = new int[] { 1, 2, 3, 4, 5, 7, 8, 3, 7 };

        for (int i = 0; i < numArray.Length; i++)
        {
            for (int j = i + 1; j < numArray.Length; j++)
            {
                if (numArray[i] == numArray[j])
                {
                   //DO SOMETHING
                }
            }

* ИЛИ вы можете отфильтровать массив и использовать рекурсивную функцию, если вы хотите получить количество вхождений *

int[] array = { 1, 2, 3, 4, 5, 4, 4, 1, 8, 9, 23, 4, 6, 8, 9, 1,4 };
int[] myNewArray = null;
int a = 1;

 void GetDuplicates(int[] array)
    for (int i = 0; i < array.Length; i++)
            {
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[i] == array[j])
                    {
                          a += 1;
                    }
                }
                Console.WriteLine(" {0} occurred {1} time/s", array[i], a);

                IEnumerable<int> num = from n in array where n != array[i] select n;
                 myNewArray = null;
                 a = 1;
                 myNewArray = num.ToArray() ;

                 break;

            }
             GetDuplicates(myNewArray);

Answer 5

Вот реализация в Python ответа @ eugensk00 (одна из его ревизий), в которой не используется модульная арифметика. Это однопроходный алгоритм, O (log (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) делает приведенный выше алгоритм нелинейным.

Answer 6

Как насчет использования https://en.wikipedia.org/wiki/HyperLogLog?

Redis делает http://redis.io/topics/data-types-intro#hyperloglogs

HyperLogLog - это вероятностная структура данных, используемая для подсчета уникальных вещей (технически это относится к оценке мощности множества). Обычно подсчет уникальных предметов требует использования объема памяти, пропорционального количеству предметов, которые вы хотите посчитать, потому что вам нужно помнить элементы, которые вы уже видели в прошлом, чтобы избежать их многократного подсчета. Однако существует набор алгоритмов, которые обменивают память на точность: в случае реализации Redis вы получаете приблизительную меру со стандартной ошибкой, которая составляет менее 1%. Волшебство этого алгоритма заключается в том, что вам больше не нужно использовать объем памяти, пропорциональный количеству подсчитанных предметов, и вместо этого вы можете использовать постоянный объем памяти! 12 Кбайт в худшем случае, или намного меньше, если ваш HyperLogLog (мы будем теперь называть их HLL) видел очень мало элементов.

Answer 7

Вот алгоритм, который использует статистику заказов и работает в O(n).

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

Вы также полагаетесь на то, что после звонка на SELECT, элементы, которые меньше или равны медиане, перемещаются влево от медианы.

• Вызовите SELECT на A с медианой в качестве параметра.
• Если значение медианы равно floor(n/2), то повторяющиеся значения соответствуют медиане. Итак, вы продолжаете с правой половины массива.
• Иначе, если это не так, то повторное значение оставляется медиане. Итак, вы продолжаете с левой половины массива.
• Вы продолжаете этот путь рекурсивно.

Например:

• Когда A={2, 3, 6, 1, 5, 4, 0, 3, 5} n=9, то медиана должна быть равна 4.
• После первого звонка SELECT
• A={3, 2, 0, 1, <3>, 4, 5, 6, 5} Среднее значение меньше, чем 4, поэтому мы продолжаем с левой половины.
• A={3, 2, 0, 1, 3}
• После второго звонка SELECT
• A={1, 0, <2>, 3, 3} тогда медиана должна быть 2, поэтому мы продолжаем с правой половины.
• A={3, 3}, найдено.

Этот алгоритм работает в O(n+n/2+n/4+...)=O(n).

Answer 8

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

в 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

Answer 9

В с:

    int arr[] = {2, 3, 6, 1, 5, 4, 0, 3, 5};

    int num = 0, i;

    for (i=0; i < 8; i++)
         num = num ^ arr[i] ^i;

Начиная с x^x=0, числа, которые повторяются нечетное количество раз, нейтрализуются. Давайте назовем уникальные номера a и b. У нас осталось a^b. Мы знаем a^b != 0, так как a != b. Выберите любой 1 бит a^b и используйте его в качестве маски, т.е. выберите x в качестве степени 2, чтобы x & (a^b) было ненулевым.

Теперь разделите список на два подсписка - один подсписок содержит все числа y с y&x == 0, а остальные идут в другом подсписке. По тому, как мы выбрали x, мы знаем, что пары a и b находятся в разных сегментах. Таким образом, теперь мы можем применить один и тот же метод, использованный выше, к каждому сегменту независимо и выяснить, что такое a и b.

Answer 10

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

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

Давайте возьмем входной массив, как показано ниже

int arr[] = {1,1,2,10,3,3,4,5,5,6,6};

числа 2,10 и 4 не повторяются, но они расположены в отсортированном порядке, если не отсортированы, сначала используйте быструю сортировку.

Позволяет применить мою программу к этому

using namespace std;

main()
{
    //int arr[] = {2, 9, 6, 1, 1, 4, 2, 3, 5};
    int arr[] = {1,1,2,10,3,3,4,5,5,6,6};

    int i = 0;

    vector<int> vec;

    int var = arr[0];
    for(i = 1 ; i < sizeof(arr)/sizeof(arr[0]); i += 2)
    {
            var = var ^ arr[i];

            if(var != 0 )
            {
                //put in vector
                var = arr[i-1];
                vec.push_back(var);
                i = i-1;
            }
            var = arr[i+1];
    }

    for(int i = 0 ; i < vec.size() ; i++)
        printf("value not repeated = %d\n",vec[i]);

}

Это дает вывод:

value not repeated= 2

value not repeated= 10

value not repeated= 4

Это просто и очень просто, просто используйте XOR man.