Нахождение дублирующего элемента в массиве?

Question

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

Дублируется одно число в массиве. Найти его

Простое решение заключается в следующем:

for(int i=0;i<n;i++){
{  
    dup = false;
    for(j=0;j<n;j++){
        if(i!=j && a[i]= a[j]){
            dup = true;
        }

       if(dup == true)
          return a[i]
     }
}

Но я хочу реализовать это за O (n log (n)) и за O (n) время. Как я могу это сделать?

Answer 1

Сортировка массива (это можно сделать в первом O (n Log n), затем просто нужно выполнить сравнение для смежных элементов. Или просто поместить массив в хеш-таблицу и остановить, если вы найдете первый ключ с большой записью.

Answer 2

Я отвечаю на "Поиск дублированного элемента в массиве?"

Вы ищете i и j от 0 до

for (int i=0; i<n-1; i++) 
{
    for (j=i+1; j<n; j++)
    {
         if (a[i] == a[j])
         {
            return i;
         }
    }
}
return -1; 

Повторная установка dup = false - нонсенс. Либо dup все еще имеет значение false, либо это было так, тогда вы оставили код с возвратом.

Answer 3

Запись предыдущих ответов в реальном коде (Java):

O (n log n) время:

    Arrays.sort(arr);
    for (int i = 1; i < arr.length; i++)
        if (arr[i] == arr[i - 1])
            return arr[i];
    throw new Exception(); // error: no duplicate

O (n) время:

    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < arr.length; i++) {
        if (set.contains(arr[i]))
            return arr[i];
        set.add(arr[i]);
    }
    throw new Exception(); // error: no duplicate

Answer 4

Найти O (n) решение для сложности, как показано ниже -

int ar[]={0,1,2,3,0,2,3,1,0,2};
    Set  <Integer>mySet=new HashSet<>();
    for(int n:ar){
        if(!mySet.add(n)){
            System.out.println(" "+n);
        }
    }

И еще один процесс с меньшей сложностью пространства O (N) и, возможно, O (n Log n) -

    public void duplicateElementSolution(int ar[]){
     Arrays.sort(ar);

    for(int i=0;i<(ar.length-1);i++){
        if(ar[i]==ar[i+1]){
            System.out.println(" "+ar[i]);
        }
    }
  }

Answer 5

Используя коллекции, мы можем перейти к фрагменту кода ниже -

Set<String> set = new HashSet<String>();
    for (String arrayElement : arr) {
        if (!set.add(arrayElement)) {
            System.out.println("Duplicate Element is : " + arrayElement);
        }
    }

Answer 6

I рекомендует использовать хеш-карту (при условии отсутствия столкновений) для ее решения.

 private boolean hasDuplicate(int[] arr) {
        Map<Integer, Boolean> map = new HashMap();
        // find the duplicate element from an array using map
        for (int i = 0; i < arr.length; i++) {
            if(map.containsKey(arr[i])) {
                return true;
            } else {
                map.put(arr[i], true);
            }
        }
        return false;
    }

Сложность времени: O (n)

Пространственная сложность: O (n)

Другой подход - сортировка и сравнение, но сортировка добавляет дополнительные издержки .

Answer 7

(Вопрос в его нынешней форме немного сбивает с толку - мой ответ предполагает, что вопрос состоит в том, чтобы найти два числа в массиве, которые суммируются с данным значением)

Поскольку данный массив не отсортирован, я предполагаю, что нам не разрешено сортировать массив (т. Е. Данный порядок массива изменить нельзя).

Самое простое решение IMHO - перебирать каждое число x и проверять, встречается ли I-x где-либо в массивах. По сути, это то, что делает ваше решение O (n ^ 2).

Это может быть уменьшено до O (n) или O (nlogn) путем ускорения поиска с использованием некоторой структуры данных с быстрой установкой. По сути, когда мы выполняем итерацию по массиву, мы запрашиваем, происходит ли в наборе I-x.

Код (на Python):

l=[1,2,3,4,5,6,7,8,9]
seen=set()

I=11
for item in l:
        if I-item in seen:
                print "(%d,%d)"%(item,I-item)
        seen.add(item)

Сложность решения зависит от сложности вставки / поиска используемой вами структуры данных set. Реализация на основе хеш-таблицы имеет сложность O (1), поэтому она дает вам алгоритм O (n), в то время как set на основе дерева приводит к алгоритму O (nlogn).

Edit:

Эквивалентная структура данных для set Python будет stl::set в C ++ и TreeSet / HashSet в Java. Строка I-x in seen будет переводиться в seen.contains(I-x) в Java и seen.find(I-x)==seen.end() в C ++.

Answer 8

Ссылка java.util.TreeSet, которая реализована в красно-черном дереве, это O (n * log (n)) .