6

这个问题仅仅是关于算法的。在伪代码中是这样的：

A = Array of strings; //let's say count(A)  = N
S = String to find;   //let's say length(S) = M

for (Index=0; Index<count(A); Index++)
  if (A[Index]==S) {
    print "First occurrence at index\x20"+Index;
    break;
  }

这个 for 循环需要字符串比较 N 次（或字节比较 N*M 次，O(N*M)）。当数组 A 有很多项或字符串 S 太长时，这很糟糕。

找出第一次出现的更好方法吗？O(K*logK) 时的某些算法是可以的，但在 O(K) 时更可取，或者在 O(logK) 时最好，其中 K 是 N 或 M。

我不介意在比较循环之前添加一些其他结构或进行一些数据处理。

4

5 回答 5

4

将字符串放入基于散列的集合中，并测试给定字符串是否包含在集合中，一旦构建集合，您应该会获得或多或少的恒定性能。

于 2012-04-28T18:40:46.877 回答
4

您可以将整个字符串数组转换为有限状态机，其中转换是字符串的字符，并将产生状态的字符串的最小索引放入状态。这需要很多时间，并且可能被认为是索引。

于 2012-04-28T18:42:49.357 回答
3

您可以首先对字符串数组进行排序，这将花费 O(m*nlogn) 时间。并且在 A 排序后，可以进行二分查找而不是线性查找，这样可以将总运行时间减少到 O(m*logn)。

这种方法的优点是很容易实现。例如，在 Java 中，您只需 2 行代码就可以做到这一点：

Arrays.sort(A);
int index = Arrays.binarySearch(A, "S");
于 2012-04-28T18:57:44.817 回答
3

您可以使用自平衡二叉搜索树。大多数实现都有 O(log(n)) 插入和 O(log(n)) 搜索。

如果你的集合不是很大，并且你的值有一个很好的散列函数，那么基于散列的集合是一个更好的解决方案，因为在这种情况下你将有 O(1) 的插入和 O(1) 的搜索。但是如果你的哈希函数不好或者你的集合太大，那么插入和搜索将是 O(n) 和 O(n)。

于 2012-04-28T19:02:57.730 回答
1

尽可能快地搜索的最佳方法是对数组进行排序正如您所描述的，似乎没有可能的先验信息允许在搜索中进行一些启发式或约束

首先对数组进行排序（例如快速排序，O(NlogN)），然后进行二分查找 O(log(N))

于 2012-04-28T19:06:13.690 回答