это эффективный алгоритм?

Question

Привет это мой алгоритм, который использует массив с числами с плавающей точкой, которые были отсортированы ранее. потому что я думал, что когда мы сортируем массив перед использованием этого алгоритма, его худший результат будет O (nlogn), но без сортировки он будет O (n ^ 2). Так что я думаю, что этот алгоритм будет в порядке для поиска одного дубликата номера. Я прав? Спасибо

1     Algorithm Duplicate_Number(a , n)
2     // Find one duplicate number in a[1 :n ]
3     {
4              temp: = a [0];
5              while (i<n) do
6              {
7                     if (temp=a[i])
8                     {
9                           return a[i]; break;
10                    }
11                    else
12                         temp: =a [++i];
13           }

Answer 1

Ну, вы никогда не определяли "i", но если ваш массив отсортирован, это будет работать для любого полностью упорядоченного типа, где есть только один правильный порядок сортировки для коллекции, а float такого типа.

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

Вы знакомы с хеш-таблицами?Эта проблема может быть решена за O (n) раз.Вам не нужно сортировать массив, поэтому вы не тратите O (n lg n) времени на его сортировку.Для каждого элемента проверьте, находится ли он уже в хэш-таблице;верните его, если он есть, и вставьте его в хеш-таблицу, если это не так.Операции вставки и чтения - это O (1) (амортизируется и при условии хорошей хэш-функции) для хэш-таблицы, поэтому она должна соответствовать вашим потребностям.Хеш-таблица не может выполнить приблизительное совпадение, хотя хеш-таблицы полезны только для поиска точных значений, поскольку они не хранят данные в отсортированном порядке.

Полностью универсальная реализация Java, которая должна работать дляЛюбой тип, который определяет значимую хеш-функцию и значащее равенство (при условии, что эталонное поведение объекта по умолчанию неверно):

import java.util.HashSet;

class DuplicateValue{
    public static <T> duplicateValue(T[] values){
        HashSet<T> store = new HashSet<T>();
        for(T item : values){
            if(store.contains(item)){
                return item;
            }
            store.add(item);
        }
        return null; //no duplicate found
    }
}

Это работает буквально для любого типа данных, поскольку Java предоставляет встроенные функции HashCode и Equals.Тем не менее, если вы используете пользовательский тип данных, обязательно переопределите .hashCode и .equals, чтобы получить значимые результаты.float не является объектом, но он может быть автоматически помещен в Float, который является

Answer 2

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

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

Answer 3

Вы не инициализировали i.

Как только это будет сделано, просмотрите массив, сравнивая каждые два «соседа».

Кроме того, так как вы используете числа с плавающей запятой, вы можете подумать, достаточно ли близки некоторые два числа ... Это не обязательно для вашего алгоритма, но если эти числа генерируются некоторыми вычислениями, это может быть полезным. Вы могли бы, например, использовать некоторые epsilon = 0.000000000000000001 или smt.

Итак, алгоритм, очень похожий на ваш, может быть:

i:= 1
tmp:= a[0];
while(i < n) {
    if(a[i] = tmp) {
        print "duplicate number: " + tmp
        break
    } else {
        tmp:=a[i]
        i++
    }
}

P.S. И да, сортировка массива - хорошая идея. Этот кусок кода имеет сложность O (n), когда используется отсортированный массив.

Answer 4

Простой цикл for будет таким же эффективным, но гораздо более читабельным:

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

Редактировать: - В этом примере используется синтаксис языка Си, но большинство языков имеют эквивалент цикла for.

Answer 5

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