algorithm - 这是一个有效的算法吗？

Question

嗨这是我的算法，它采用之前排序的 float 数组。因为我认为当我们在使用该算法之前对数组进行排序时；它的最坏情况下的性能将是 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 就是这样一种类型。

p>

float 很少彼此完全相等，特别是如果它们事先经过任何实际的计算步骤。通常最好检查 float 是否在彼此的小范围内，以处理由于四舍五入而导致的一些不可避免的计算错误。如果您没有提前执行计算步骤而只是接受输入，这应该可行。

您熟悉哈希表吗？这个问题可以在 O(n) 时间内解决。您不需要对数组进行排序，因此您不需要花费 O(n lg n) 时间对其进行排序。对于每个元素，检查它是否已经在哈希表中；如果是则返回它，如果不是则将其插入到哈希表中。插入和读取操作在散列表上是 O(1)(摊销，并假设一个好的散列函数)，因此应该满足您的需要。哈希表不能进行近似相等匹配，尽管哈希表只对精确值查找有用，因为它们不按排序顺序保存数据。

一个完全通用的 Java 实现，应该适用于定义有意义的散列函数和有意义的等号的任何类型(假设 Object 的默认引用行为是错误的):

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，也就是。