查找具有不同权重的对象的算法

Question

我们给了N个对象，其中一个对象恰好具有不同的权重（可以更少或更多）。此外，我们还提供了以下3种类型的M个比较-

1. 重量（A组）<重量（B组）
2. 重量（A组）>重量（B组）
3. 重量（A组）=重量（B组）

其中集合A和集合B（都具有相同数量的对象）是从最初的N个对象开始的对象列表。

给定M这样的比较，如果可能的话，我需要找到重量不同的物体。否则，请说明给定的M个比较列表不足以检测权重不同的列表。

有人可以提出解决这个问题的算法吗？

Answer 1

我认为您可以使用比建议的算法更简单的算法，因为您知道一个对象具有不同的权重。

为每个对象管理两个标志，以指示它们是否可能更重或更轻（因此最初未设置它们）。迭代所有给定的比较并按如下方式设置标志：

1. A < B：为 A 中的所有对象设置较轻的标志，为 B 中的所有对象设置较重的标志。
2. A > B：为 A 中的所有对象设置较重标志，为 B 中的所有对象设置较轻标志。
3. A = B：为 A 和 B 中的所有对象设置两个标志。

现在，您可以通过对对象（即它们的标志）进行一次迭代来找到解决方案，但这有点棘手，因为当您只有相等性并且只有一个对象从未出现在任何比较中时，它必须是解决方案：

1. 初始化solution = null,, noFlagSolution = null.noFlagCount = 0​

2. 迭代对象：

   • 如果两个标志均已设置：继续。
   • 如果没有设置标志：noFlagSolution = current,noFlagCount++
   • 如果设置了一个标志：
     • 如果solution != null：返回null（我们有多个候选人）。
     • 别的：solution = current

3. 如果solution != null：返回solution（在这种情况下我们还可以判断物体是更重还是更轻）。

4. if noFlagCount == 1: return noFlagSolution(上面提到的特殊情况，这里我们不知道唯一的候选者是更重还是更轻)。

5. 否则没有唯一的解决方案。