Java 在数组中搜索匹配的字符串

Question

如何优化以下内容:

final String[] longStringArray = {"1","2","3".....,"9999999"};
String searchingFor = "9999998"
for(String s : longStringArray)
    {
        if(searchingFor.equals(s))
        {
            //After 9999998 iterations finally found it
            // Do the rest of stuff here (not relevant to the string/array)
        }
    }

注意:longStringArray 在每个运行时只被搜索一次并且没有排序并且在我运行程序时每次都不同。

我确定这里有一种方法可以改善最坏情况下的性能，但我似乎找不到...

附言也希望有一个解决方案，其中字符串 searchingFor 不存在于数组 longStringArray 中。

谢谢。

Answer 1

好吧，如果您必须使用一个数组，但您不知道它是否已排序，并且您只打算进行一次查找，那么它总是一个 O(N ) 手术。你对此无能为力，因为任何优化步骤至少是 O(N) 开始 - 例如填充集合或对数组进行排序。

其他选项:

• 如果数组已排序，您可以执行二分查找。这会将每个查找变成 O(log N) 操作。
• 如果您要进行多个搜索，请考虑使用 HashSet<String> .这会将每次查找变成 O(1) 操作(假设碰撞很少)。