这是一个有效的算法吗？

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,即.