1

使用 JavaScript 表示法：

A = {color:'red',size:8,type:'circle'};

L = [{color:'gray',size:15,type:'square'},
     {color:'pink',size:4,type:'triangle'},
     {color:'red',size:8,type:'circle'},
     {color:'red',size:12,type:'circle'},
     {color:'blue',size:10,type:'rectangle'}];

这种情况的答案是 2，因为 L[2] 与 A 相同。您可以通过测试每种可能性在 O(n) 中找到答案。什么是可以更快地找到答案的表示/算法？

4

4 回答 4

1

我只需创建一个 HashMap 并将所有对象放入 HashMap 中。我们还需要定义一个哈希函数，它是对象中数据的函数（类似于在 java 中覆盖 Object.hashcode()）

假设给定数组 L 是 [B, C, D]，其中 B、C 和 D 是对象。那么 HashMap 将是 {B=>1, C=>2, D=>3}。现在假设 D 是 A 的副本。所以我们只需在这张地图中查找 A 并得到答案。同样正如 Eric P 在评论中所建议的那样，我们需要根据数组 L 中的任何更改保持哈希图的更新。这也可以在 O(1) 中对数组 L 中的每个操作完成。

在 HashMap 中查找对象的成本是 O(1)。所以我们可以实现 O(1) 复杂度。

于 2012-09-02T19:00:52.800 回答
0

我认为不可能比O(n)您的先决条件更快地做到这一点。使用二分搜索可以找到元素O(logn)，但是：

  • A）您需要具有一个变量的元素进行比较
  • B）按该变量排序的列表

也许通过一些技术（排序、跳过列表等），您可以比 N 次迭代更快地找到答案，但最坏的情况是O(n)

于 2012-09-02T18:58:28.110 回答
0

由于目标是找到所有对象是 A 的克隆，因此您必须对每个对象至少测试一次以确定它是否是 A 的克隆，因此最小测试次数为 N。通过列表一次并测试每个对象执行 N 次测试，因此由于该方法是最少的测试次数，因此它是一种最优方法。

于 2012-09-02T19:14:45.397 回答
-1

首先，我假设您在谈论数组，而不是列表。“list”这个词是为特定类型的数据结构保留的，它具有 O(n) 索引复杂性，因此同时在其中的任何搜索至少是线性的。

对于未排序的数组，唯一的算法是线性时间的全扫描。但是，如果数组已排序，则可以使用二进制或插值搜索来获得更好的时间。

排序数组的问题在于它们具有线性插入时间。不好。因此，如果您希望更新您的集合并且更新和搜索时间都很重要，您应该搜索优化的容器，在 c++ 和 haskell 中调用Set（分别在头文件中的set模板和包中的模块）。我不知道JS中有没有。setData.Setcontainers

于 2012-09-02T21:14:13.733 回答