Найти дубликат элемента в массиве за время O(n)

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

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

за один проход через вектор вычислите сумму всех чисел и сумму квадратов всех чисел.

вычесть сумму всех чисел из N(N-1)/2. Назовем это A.

вычесть сумму квадратов от N(N-1)(2N-1)/6. Разделите это на A. Вызов результат B.

номер, который был удален (B + A)/2 и номер, который он был заменен на (B - A)/2.

пример:

вектор [0, 1, 1, 2, 3, 5]:

• N = 6

• сумма вектора 0 + 1 + 1 + 2 + 3 + 5 = 12. N (N-1)/2 равно 15. А = 3.

• сумма квадратов 0 + 1 + 1 + 4 + 9 + 25 = 40. N(N-1) (2N-1)/6 равно 55. B = (55-40) / A = 5.

• номер, который был удален (5 + 3) / 2 = 4.

• номер, на который он был заменен (5 - 3) / 2 = 1.

почему это работает:

• сумма исходного вектора [0, ..., N-1] и N(N-1)/2. Предположим, что значение a был удален и заменен b. Теперь сумма модифицированного вектора будет N(N-1)/2 + b - a. Если вычесть сумму модифицированного вектора из N(N-1)/2 мы получаем a - b. Так что A = a - b.

• аналогично, сумма квадратов исходного вектора N(N-1)(2N-1)/6. Сумма квадратов модифицированного вектора равна N(N-1)(2N-1)/6 + b2 - a2. Вычитание суммы квадратов модифицированного вектора из исходной суммы дает a2 - b2, что то же самое, что (a+b)(a-b). Так что если мы разделим его на a - b (то есть,A), мы получаем B = a + b.

• теперь B + A = a + b + a - b = 2a и B - A = a + b - (a - b) = 2b.

вы можете сделать это в o(n) времени без какого-либо дополнительного пространства. Вот как работает алгоритм:

перебираем массив следующим образом:

1. для каждого встреченного элемента установите соответствующее значение индекса в отрицательное. Например : если вы найдете[0] = 2. Добрался до[2] и отрицает значение.

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

2. проверьте, если индекс, соответствующий значению, уже помечен отрицательным, если да, вы получаете дублированный элемент. Например: если a[0]=2 , Перейдите к A[2] и проверьте, является ли он отрицательным.

допустим у вас есть следующий массив :

int a[]  = {2,1,2,3,4};

после первого элемента массива будет :

int a[] = {2,1,-2,3,4};

после второго элемента Ваш массив будет:

int a[] = {2,-1,-2,3,4};

когда вы достигнете третьего элемента, вы перейдете к[2] и увидите его уже отрицательно. Вы получаете дубликат.

сканировать массив 3 раза:

1. XOR вместе все элементы массива ->A. XOR вместе все числа от 0 до N-1 ->B. Сейчас A XOR B = X XOR D, где X-удаленный элемент, А D-дублирующий элемент.
2. выбираем любой ненулевой бит в A XOR B. XOR вместе все элементы массива, где этот бит установлен ->A1. XOR вместе все числа от 0 до N-1, где этот бит установлен -> B1. Сейчас A1 XOR B1 = X или A1 XOR B1 = D.
3. сканируйте массив еще раз и попробуйте найтиA1 XOR B1. Если он найден, это дубликат элемента. Если нет, то дубликат элемента A XOR B XOR A1 XOR B1.

Я предлагаю использовать BitSet. Мы знаем, что N достаточно мал для индексации массива, поэтому битовый набор будет иметь разумный размер.

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

использовать HashSet для хранения всех уже виденных чисел. Он работает в (амортизированном)O(1) время, так что Итого O(N).

использовать хеш-таблицу. Включение элемента в хэш-таблицу - Это O (1).

одно рабочее решение:

число asume-это целые числа

создать массив [0 .. N]

int[] counter = new int[N];

затем повторите чтение и увеличьте счетчик:

 if (counter[val] >0) {
   // duplicate
 } else {
   counter[val]++;
 }

@rici прав насчет использования времени и пространства: "Это можно сделать в O(n) времени и O(1) пространстве."

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

OJ ставит его таким образом здесь: (Примечание 3 видимо можно сузить)

задан массив чисел, содержащий n + 1 целых чисел, где каждое целое число находится между 1 и n (включительно), доказать, что по крайней мере один дубликат номера должен существовать. Предположим, что существует только один дубликат номера, найти дубликат один.

Примечание:

• вы не должны изменять массив (предположим, что массив только для чтения).
• вы должны использовать только константу, O (1) дополнительное пространство.
• ваша сложность выполнения должна быть меньше, чем O(n2).
• есть только один дубликат номера в массиве, но он может быть повторен больше и не один раз.

вопрос очень хорошо объяснил и ответил:здесь Кит Шварц, используя цикл Флойда-поиск:

основной трюк, который нам нужно использовать для решения этой проблемы, заключается в том, чтобы заметить, что поскольку у нас есть массив из n элементов в диапазоне от 0 до n - 2, мы можем думать о массиве как об определении функции f из множества {0, 1,..., n-1} на себя. Эта функция определена по f (i) = A[i]. Учитывая эту настройку, Дублированное значение соответствует паре индексов i != j такое, что f(i) = f(j). Поэтому наша задача-найти эту пару (i, j). Как только мы его получим, мы можем легко найти Дублированное значение, просто выбрав f(i) = A[i].

но как нам найти это повторяющееся значение? Оказывается, это хорошо изученная проблема в информатике под названием Обнаружение циклов. Общая форма задачи заключается в следующем. Нам дана функция f. Определите последовательность x_i как

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

предполагая, что F отображает из домена в себя, эта функция будет иметь одну из трех форм. Во-первых, если область бесконечна, то последовательность может быть бесконечно длинной и неповторяющейся. Например, функция f (n) = n + 1 на целых числах обладает этим свойством - ни одно число никогда не дублируется. Во-вторых, последовательность может быть замкнутого цикла, что означает, что есть некий я, так что x_0 = x_i. В этом случае последовательность циклы через некоторый фиксированный набор значений бесконечно. Наконец, последовательность может быть " РО-образной."В данном случае последовательность выглядит примерно так:

 x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                    ^                       |
                    |                       |
                    +-----------------------+

также можно найти реализацию python здесь:

def findDuplicate(self, nums):
    # The "tortoise and hare" step.  We start at the end of the array and try
    # to find an intersection point in the cycle.
    slow = 0
    fast = 0

    # Keep advancing 'slow' by one step and 'fast' by two steps until they
    # meet inside the loop.
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Start up another pointer from the end of the array and march it forward
    # until it hits the pointer inside the array.
    finder = 0
    while True:
        slow   = nums[slow]
        finder = nums[finder]

        # If the two hit, the intersection index is the duplicate element.
        if slow == finder:
            return slow

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

пусть X быть недостающее число и R быть повторяющиеся числа.

1. мы можем предположить, что от [1..n], т. е. ноль не появляется. Фактически, при циклическом прохождении через массив мы можем проверить, был ли найден ноль и сразу же вернуться если нет.

2. теперь считаем:

   sum(A) = n (n + 1) / 2 - X + R
   
   product(A) = n! R / X
   

здесь product(A) является продуктом всех элементов в A пропуск нуля. У нас есть два уравнения с двумя неизвестными, из которых X и R можно вывести алгебраически.

Edit: по многочисленным просьбам, вот отработанный пример:

давайте:

S = sum(A) - n (n + 1) / 2
P = n! / product(A)

тогда наши уравнения становятся:

R - X = S
X = R P

что можно решить:

R = S / (1 - P)
X = P R = P S / (1 - P)

пример:

A = [0 1 2 2 4]

n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2

R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3

вы можете действовать следующим образом:

1. сортировка массива с помощью алгоритма сортировки по линейному времени (например, подсчет сортировки) - O (N)
2. сканирование отсортированного массива и остановка, как только два последовательных элемента равны - O(N)

public class FindDuplicate {
    public static void main(String[] args) {
        // assume the array is sorted, otherwise first we have to sort it.
        // time efficiency is o(n)
        int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
        int count = 1;
        int element1;
        int element2;

        for (int i = 0; i < elementData.length - 1; i++) {
            element1 = elementData[i];
            element2 = elementData[count];
            count++;
            if (element1 == element2) {
                System.out.println(element2);
            }
        }
    }
}

  public void duplicateNumberInArray {
    int a[] = new int[10];
    Scanner inp = new Scanner(System.in);
    for(int i=1;i<=5;i++){  
        System.out.println("enter no. ");
        a[i] = inp.nextInt();
    }
    Set<Integer> st = new HashSet<Integer>();
    Set<Integer> s = new HashSet<Integer>();
    for(int i=1;i<=5;i++){          
        if(!st.add(a[i])){
            s.add(a[i]);
        }
    }

    Iterator<Integer> itr = s.iterator();
                System.out.println("Duplicate numbers are");
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

прежде всего создание массива целых чисел с помощью класса сканера. Затем повторите цикл через числа и проверьте, можно ли добавить число в set (числа могут быть добавлены в set только тогда, когда это конкретное число не должно быть уже установлено, означает, что set не позволяет дублировать no. чтобы добавить и вернуть логический vale FALSE при добавлении повторяющегося значения).Если нет. невозможно добавить означает, что он дублируется, поэтому добавьте этот дубликат в другой набор, чтобы мы могли печатать позже. Пожалуйста обратите внимание на то, что мы добавляем повторяющееся число в набор, потому что может быть возможно, что повторяющееся число может повторяться несколько раз, поэтому добавьте его только once.At последний мы печатаем набор с помощью итератора.

//это похоже на подход HashSet, но использует только одну структуру данных:

    int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();

    for (int i : a) {
        map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
    }

    Set<Entry<Integer, Integer>> es = map.entrySet();
    Iterator<Entry<Integer, Integer>> it = es.iterator();

    while (it.hasNext()) {
        Entry<Integer, Integer> e = it.next();
        if (e.getValue() > 1) {
            System.out.println("Dupe " + e.getKey());
        }
    }

мы можем эффективно использовать hashMap:

Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
    if (map.containsKey(x))  map.put(x,map.get(x)+1);
    else map.put(x,1);
}

Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
    if(map.get(x)!=1)
    {
        System.out.println(x+" repeats : "+map.get(x));
    }
}

эта программа основана на c#, и если вы хотите сделать эту программу с помощью другого языка программирования, вы должны сначала изменить массив в порядке добавления и сравнить первый элемент со вторым элементом.Если он равен, то повторное число найдено.Программа-это

int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
  if(array[a]==array[a+1]
  {
     Console.WriteLine("This {0} element is repeated",array[a]);
   }
}
Console.WriteLine("Not repeated number in array");

1. сортировать массив O (n ln n)

2. используя трюк скользящего окна, чтобы пересечь массив O (n)

   Пробел-Это O (1)

   Arrays.sort(input);
   for(int i = 0, j = 1; j < input.length ; j++, i++){
       if( input[i] == input[j]){
           System.out.println(input[i]);
           while(j < input.length && input[i] == input[j]) j++;
           i = j - 1;
       }
   }
   

тест инт[] { 1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7 }

выход 1, 2, 3, 7

пройдите через массив и проверьте знак array[abs(array[i])], если положительный сделать его отрицательным и если он отрицательный, то распечатать его, следующим образом:

import static java.lang.Math.abs;

public class FindRepeatedNumber {

    private static void findRepeatedNumber(int arr[]) {
        int i;
        for (i = 0; i < arr.length; i++) {
            if (arr[abs(arr[i])] > 0)
                arr[abs(arr[i])] = -arr[abs(arr[i])];
            else {
                System.out.print(abs(arr[i]) + ",");
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        findRepeatedNumber(arr);
    }
}

ссылки: http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

как описано,

у вас есть массив чисел от 0 до n-1, одно из чисел удалены, и заменены на число уже в массиве, который делает a дубликат этого номера.

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

        public static void main(String[] args) {
    //int arr[] = { 0, 1, 2, 2, 3 };
    int arr[] = { 1, 2, 3, 4, 3, 6 };
    int len = arr.length;
    int iMax = arr[0];
    for (int i = 1; i < len; i++) {
        iMax = Math.max(iMax, arr[i]);
        if (arr[i] < iMax) {
            System.out.println(arr[i]);
            break;
        }else if(arr[i+1] <= iMax) {
            System.out.println(arr[i+1]);
            break;
        }
    }
}

• O(n) время и O (1) пространство ;пожалуйста, поделитесь своими мыслями.

int a[] = {2,1,2,3,4};

int b[] = {0};

for(int i = 0; i < a.size; i++)
{

    if(a[i] == a[i+1])
    {
         //duplicate found
         //copy it to second array
        b[i] = a[i];
    }
}