algorithm - 给定一个对象 A 和一个对象列表 L，如何在不测试所有情况的情况下找出 L 上的哪些对象是 A 的克隆？

Question

使用 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) 中找到答案。可以更快找到答案的表示/算法是什么？

Answer 1

我会创建一个 HashMap 并将所有对象放入 HashMap 中。我们还需要定义一个散列函数，它是对象中数据的函数(类似于在 java 中重写 Object.hashcode())

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

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