Алгоритм поиска дубликатов в массиве

Question

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

 FindingDuplicateAlgorithm(A) // A is the array
      mergeSort(A);
      for  int i <- 0 to i<A.length
           if A[i] == A[i+1]
                 i++
               return  A[i]
           else
                 i++

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

Answer 1

Для обработки дубликатов вы можете сделать следующее:

if A[i] == A[i+1]:
    result.append(A[i]) # collect found duplicates in a list
    while A[i] == A[i+1]: # skip the entire range of duplicates 
        i++               # until a new value is found

Answer 2

Вы хотите найти Дубликаты в Java?

Вы можете использовать HashSet.

HashSet h = new HashSet();
for(Object a:A){
   boolean b = h.add(a);
   boolean duplicate = !b;
   if(duplicate)
       // do something with a;
}

Возвращаемое значение add () определяется как:

true, если набор еще не содержит указанный элемент.

РЕДАКТИРОВАТЬ: Я знаю, что HashSet оптимизирован для вставок и содержит операции.Но я не уверен, достаточно ли это быстро для ваших проблем.

EDIT2: Я видел, как вы недавно добавили тег домашней работы.Я не предпочел бы мой ответ, если это домашнее задание, потому что это может быть "высокий уровень" для урока по всем алгоритмам

http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html#add%28java.lang.Object%29

Answer 3

Ваш ответ кажется довольно хорошим.Первая сортировка и их простая проверка соседних значений дает вам O(n log(n)) сложность, которая весьма эффективна.

Сортировка слиянием равна O(n log(n)), тогда как проверка соседних значений просто O(n).

* 1007(как упомянуто в одном из комментариев) вы получите переполнение стека (lol) с вашим псевдокодом.Внутренний цикл должен быть (в Java):

for (int i = 0; i < array.length - 1; i++) {
    ...
}

Кроме того, если вы действительно хотите отобразить, какие числа (и / или индексы) являются дубликатами, вам нужно будет сохранить их в отдельном списке.

Answer 4

 public void printDuplicates(int[] inputArray) {
    if (inputArray == null) {
        throw new IllegalArgumentException("Input array can not be null");
    }
    int length = inputArray.length;

    if (length == 1) {
        System.out.print(inputArray[0] + " ");
        return;
    }

    for (int i = 0; i < length; i++) {

        if (inputArray[Math.abs(inputArray[i])] >= 0) {
            inputArray[Math.abs(inputArray[i])] = -inputArray[Math.abs(inputArray[i])];
        } else {
            System.out.print(Math.abs(inputArray[i]) + " ");
        }
    }
}

Answer 5

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

Answer 6

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

Answer 7

Ваш алгоритм содержит переполнение буфера.i начинается с 0, поэтому я предполагаю, что индексы в массиве A начинаются с нуля, т.е. первый элемент - A[0], последний - A[A.length-1].Теперь i считает до A.length-1, и в теле цикла обращается к A[i+1], который находится вне массива для последней итерации.Или, проще говоря: если вы сравниваете каждый элемент со следующим элементом, вы можете выполнять только сравнения длины 1.

Если вы хотите сообщить о дубликатах только один раз, я бы использовал переменную bool firstDuplicate, это установлено в false, когда вы находите дубликат, и true, если число отличается от следующего.Тогда вы только сообщите о первом дубликате, сообщив только дубликаты номеров, если firstDuplicate истинно.