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

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. 如果noFlagCount == 1:返回noFlagSolution(上面提到的特殊情况，这里我们不知道唯一的候选者是更重还是更轻) .

5. 否则无唯一解。