Найти дубликаты в массиве

Question

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

С дополнительным пробелом это означает дополнительный пробел порядка O (n).

Помогает ли оператор Xor каким-либо образом.

Answer 1

Отказ от ответственности

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

Чтобы начать наше визуальное мышление, давайте возьмем примерный массив: 50 100 150 -2 -1 0 1 2 3 4.Как вы наверняка можете сказать, у него нет дубликатов, поэтому наш алгоритм должен вывести FALSE.Кроме того, его длина равна 10.

Шаг A: Подсчет за O (N) времени

Давайте пока проигнорируем дополнительное ограничение памяти (на самом деле, действительно нарушим его, предполагая, чтоможет иметь O(\inf) дополнительной памяти :) и сохранять в вымышленном бесконечном массиве (он также вдвойне-бесконечен, так как допускает и отрицательные значения) счетчики для каждого целого числа.Для нашего ввода этот массив будет выглядеть следующим образом:

...000001111111000...00100...00100...001000000...
        ^              ^               ^
   [index  -2]     [index  50]     [index 150]

Если какой-либо из элементов массива больше 1, то у нас есть дубликат, и алгоритм должен вернуть TRUE.

Шаг B: сопоставить -inf..inf с 0..N за O (N) время

Давайте предположим, что у нас есть карта f(x):-inf..inf -> 0..N, которая может сжимать наш бесконечный массив в массивразмер N, и, кроме того, сделать это за O (N) время.Это то, что идеально подходит для хеширования.Обратите внимание, что мы не заботимся о поддержании порядка массива, так как нас заботит только то, имеет ли он элементы выше 1. Таким образом, мы можем объединить эти два шага и устранить необходимость в бесконечной памяти - ура!Мы все еще используем дополнительную O (N) память (фактически, точно N счетчиков), чтобы сохранить значения счетчика.Следующий шаг избавился бы от этого.

Шаг C: Использование первого элемента в качестве переключателя

Прежде чем я объясню этот шаг, обратите внимание, что нам на самом деле не нужно хранить какие-либо значения, превышающие1. В первый раз, когда мы хотим увеличить счетчик, и мы заметили, что он уже имеет значение 1, мы знаем, что нашли дубликат!Так что 1 бит памяти на счетчик достаточно.Это уменьшает требуемую память до O (LG (N)), но мы на самом деле не заботимся об этом, так как она недостаточно хороша.Важной частью является то, что 1 бит памяти на счетчик является достаточным.

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

Теперь мы можем использовать сохраненный первый элемент sw и преобразованный массив для кодирования в счетчиках отшаг подсчета (шаги A + B) следующим образом: рассматривая элемент с индексом k из A, если A[f(A[k])] < A[f(A[k])] xor sw, то счет равен zero, что означает, что элемент, который мы рассматриваем - A[k] - имеетне было замечено ранее, поэтому мы изменили A[f(A[k])] на A[f(A[k])] xor sw.Если в противном случае A[f(A[k])] > A[f(A[k])] xor sw, то число равно one, что означает, что элемент, который мы рассматриваем - A[k] - уже был замечен ранее, поэтому он является дубликатом.

Предполагается, что карта:

f(-2 xr 50) -> 0
f(-1 xr 50) -> 1
f(0)        -> 2
f(1)        -> 3
f(2)        -> 4
f(3)        -> 5
f(4)        -> 6
f(86)       -> 7
f(150)      -> 8
f(1337)     -> 9

и после выполнения шагов в следующем порядке: step c; step a+b входной массив выглядит так:

50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory]
0     86      150      -2 xr 50     -1 xr 50     0     1     2     3     4     [state after step c]
0     86     *164*     -2 xr 50     -1 xr 50     0     1     2     3     4     [counted element 0]
0     86      164      -2 xr 50     -1 xr 50     0     1    *48*   3     4     [counted element 1]
0     86      164      -2 xr 50     -1 xr 50     0     1     48   *49*   4     [counted element 2]
*50*  86      164      -2 xr 50     -1 xr 50     0     1     48    49    4     [counted element 3]
50   *100*    164      -2 xr 50     -1 xr 50     0     1     48    49    4     [counted element 4]
50    100    !164!     -2 xr 50     -1 xr 50     0     1     48    49    4     [counted element 5]

Попытка подсчитать элемент с индексом 5, равным 0мы видим, что в массиве уже было 0!(потому что A[f(A[5])] равно 164, что больше 164 xr 50). Таким образом, мы выводим TRUE, и алгоритм заканчивается.

Мораль истории

Если нам не позволено достаточноmemory x time мы обязаны что-то забыть и ошибиться.

Извините

К сожалению, у нас нет идеальной хеш-функции, и мы не можем просто создать память из воздуха, поэтому традиционный подход не будет работать при требуемых ограничениях.Алгоритм, на который указывает ответ, заданный OP, может быть изменен таким образом, чтобы он позволял использовать числа, которые интерпретируются как независимые значения массива, выходили бы за пределы массива, учитывая идеальную хеш-функцию.Но даже тогда нужно придумать, как использовать его для обнаружения дублирования, а не find , который гарантированно существует ...

В любом случае, интересная проблема.

Answer 2

public static void getDuplicatesElements (Integer arr[]){

    //Status array to track the elements if they are already considered
    boolean status[] = new boolean [arr.length];

    //Flag to mark the element found its duplicate
    boolean dupFlag = false;

    //Output string
    String  output = "";

    //Count of duplicate elements found
    int count = 0;

    //Initialize status array with all false i.e. no duplicates
    for (int i = 0; i < arr.length; i++)
    {
        status[i] = false;
    }

    //first loop to check every element
    for (int i = 0; i < arr.length - 1; i++)
    {
        //Initialize every element to no duplicate
        dupFlag = false;

        //Check if this element is not already found duplicate, if not, check now.
        if (!status[i]){
            for (int j = i+1; j <  arr.length; j++){
                if (arr[i] == arr[j]){
                    dupFlag = true;
                    status[j] = true;
                }
            }
        }

        if (dupFlag){
            output = output + " " + arr[i];
            count++;
        }
    }

    System.out.println("Duplicate elements: " + output );
    System.out.println("Count: " + count );

}

Answer 3

import java.util.HashSet;
import java.util.Set;


public class FindDups {
public static void main(String[] args) {
    int a[]={1,2,3,3,4};

    Set<Integer> s=new HashSet<Integer>();
    for(int i=0;i<a.length;i++)
    {
    if(!s.add(a[i]))
        System.out.println("at index"+ i+" "+a[i]+"is duplicate");  
    }
    for(int i:s)
    {
        System.out.println(i);
    }
}
}