Как мы можем найти повторное число в массиве в O (n) времени и сложности O (1) пространства

Question

Как мы можем найти повторяющееся число в массиве за O (n) время и O (1) сложность?Например, массив 2,1,4,3,3,10 вывод 3

РЕДАКТИРОВАТЬ: я пытался следующим образом.я обнаружил, что если нет странным образом повторяется, то мы можем достичь результата, выполнив xor.поэтому я подумал сделать элемент, который является нечетным, не повторяющимся и даже не равным, а каждый равномерно повторяющимся, нет и нечетным. Но для этого мне нужно найти уникальный массив элементов из входного массива в O (n), но не смог найти путь.

Answer 1

Предполагая, что для значений чисел в массиве существует повышенная граница (что имеет место со всеми встроенными целочисленными типами во всех языках программирования, которые я когда-либо использовал - например, допустим, что они 32 -бит целых чисел) существует решение, которое использует постоянное пространство:

1. Создайте массив из N элементов, где N - верхняя граница для целочисленных значений во входном массиве, и инициализируйте все элементы как 0 или false или некоторый эквивалент. Я назову это массивом lookup .
2. Цикл по входному массиву и использование каждого числа для индексации в массиве поиска. Если найденное значение равно 1 или true (и т. Д.), Текущее число во входном массиве является дубликатом.
3. В противном случае установите соответствующее значение в массиве поиска на 1 или true, чтобы помнить, что мы видели этот конкретный входной номер.

Технически , это O (n) время и O (1) пространство, и оно не разрушает входной массив. Практически, вам нужно, чтобы все шло как по маслу, чтобы такая программа действительно работала (например, не может быть и речи, если речь идет о 64-битных целых числах во входных данных).

Answer 2

Не зная больше о возможных значениях в массиве, вы не можете.

При наличии O (1) места требуется самый быстрый способ сортировки массива, чтобы он был не менее O (n *журнал (п)).

Answer 3

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

1. Проверьте, равна ли маска 1, сместив значение с i.
2. Если это так, распечатайте повторное значение i.
3. Если значение не установлено, установите его.

* Если вы хотите показать одно повторное значение только один раз,добавьте еще одно целочисленное представление и установите его биты, как в примере ниже.

** Это в java, я не уверен, что мы дойдем до него, но вы можете также добавить проверку, используя Integer.MAX_VALUE.

    public static void repeated( int[] vals ) {
        int mask = 0;
        int show = 0;
        for( int i : vals ) {
            // get bit in mask
            if( (( mask >> i ) & 1) == 1 &&
                (( show >> i ) & 1) == 0 )
            {
                System.out.println( "\n\tfound: " + i );
                show = show | (1 << i);
            }

            // set mask if not found
            else
            {
                mask = mask | (1 << i);
                System.out.println( "new: " + i );
            }

            System.out.println( "mask: " + mask );
        }
    }

Answer 4

Это возможно, только если у вас есть конкретные данные.Например, все числа имеют небольшой диапазон.Затем вы можете сохранить повторную информацию в исходном массиве, не влияя на весь процесс сканирования и анализа.

Упрощенный пример: вы знаете, что все числа меньше 100, тогда вы можете пометить число повторений для числа, используя дополнительные нули, например, поставить 900 вместо 9, когда 9 встречается дважды.

Это просто, когда NumMax-NumMin

http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/

Answer 5

public static string RepeatedNumber()
    {
        int[] input = {66, 23, 34, 0, 5, 4};
        int[] indexer = {0,0,0,0,0,0}
        var found = 0;
        for (int i = 0; i < input.Length; i++)
        {
            var toFind = input[i];
            for (int j = 0; j < input.Length; j++)
            {
                if (input[j] == toFind && (indexer[j] == 1))
                {
                    found = input[j];
                }
                else if (input[j] == toFind)
                {
                    indexer[j] = 1;
                }
            }

        }


    return $"most repeated item in the array is {found}";

}

Answer 6

Я тоже столкнулся с проблемой, и мое решение использует hashMap. Версия Python следующая:

  def findRepeatNumber(lists):
      hashMap = {}
      for i in xrange(len(lists)):
          if lists[i] in hashMap:
              return lists[i]
          else: 
              hashMap[lists[i]]=i+1
      return

Answer 7

Вы можете сделать это

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main ()
{
    clrscr();
    int array[5],rep=0;
    for(int i=1; i<=5; i++)
    {
        cout<<"enter elements"<<endl;
        cin>>array[i];
    }
    for(i=1; i<=5; i++)
    {
        if(array[i]==array[i+1])
        {
            rep=array[i];
        }
    }
    cout<<" repeat value is"<<rep;
    getch();
}

Answer 8

Это невозможно без знания каких-либо ограниченных правил для входного массива: либо сложность памяти будет зависеть от размера ввода, либо сложность времени будет выше.

2 ответа вышеНа самом деле, лучшие ответы для того, чтобы приблизиться к тому, что вы просили, компромисс - время, когда второй компромисс находится в памяти, но вы не можете запустить его за O (n) время и сложность O (1) в НЕКОТОРЫМ НЕИЗВЕСТНОМ ВХОДНОМ массиве.