algorithm - 两组三个数字是否至少有两个相同的数字？

Question

我只需要编写一个看起来很容易编写的函数，但当我真正做到时，结果却比我预期的要复杂得多。这真的很困扰我，我觉得有更好的解决方案，但我的大脑正在疯狂地想它，所以我求助于你们这些好人。

基本上，我有 2 个三角形，我想知道它们是否共享一条公共(public)边。三角形由它们的顶点索引(即它们的顶点只是包含实际坐标的数组的索引)，因此归结为查找两组三个数字是否有两个共同的数字。 IE。三角形 (1,2,3) 和 (3,1,5) 共享一条边，即 (1,3) 边。但是，三角形 (1,2,3) 和 (1,5,6) 不共享一条边(只有一个顶点)，(1,2,3) 和 (4,5,6) 也不共享。

你会怎么写这个“公共(public)函数中的两个数字”？您可以假设每个集合内的所有值都是不同的(即 (1, 1, 2) 不会成为输入)，您还可以假设两个集合彼此不相等(即我不打算比较(1,2,3) 和 (1,3,2)，因为这两个是同一个三角形)。但是，不能对顺序做出任何假设，它们没有排序或类似的东西。

这基本上就是我想出的(假设集合是 (x0, x1, x2) 和 (y0, y1, y2)):

// If the x0 is equal to any of (y0, y1, y2), make sure at least one of (x1, x2)
// is equal to one of the y numbers
if (x0 == y0) {
    return x1 == y1 || x1 == y2 || x2 == y1 || x2 == y2;
} else if (x0 == y1) {
    return x1 == y0 || x1 == y2 || x2 == y0 || x2 == y2;
} else if (x0 == y2) {
    return x1 == y0 || x1 == y1 || x2 == y0 || x2 == y1;
} else {

    // if x0 is not equal to any of (y0, y1, y2), then x1 and x2 both have
    // to be equal to two of the y numbers. 
    return (x1 == y0 && x2 == y1) 
        || (x1 == y0 && x2 == y2)
        || (x1 == y1 && x2 == y0)
        || (x1 == y1 && x2 == y2)
        || (x1 == y2 && x2 == y0)
        || (x1 == y2 && x2 == y1);
}

但我觉得很血腥!这么多的分支和这么长的 bool 语句!我觉得我缺少一个明显的简单解决方案，这让我发疯。

此外，这发生在对性能非常敏感的应用程序的内部循环中，因此性能(分支、算术等)很重要。

顺便说一句，我正在编写的代码是 C#，但问题在任何命令式语言中或多或少都是相同的。

编辑:

我根据目前的建议整理了一个快速基准(这里是 code)。以下是结果(在一百万个随机三角形对上运行它):

Original method result:         7035, time elapsed in ms:   8.6252
qwertyman method result:        7035, time elapsed in ms:   8.2537
midjji method result:           7035, time elapsed in ms:   8.7984
Single HashSet method result:   7035, time elapsed in ms:   184.4984
Many HashSets method result:    7035, time elapsed in ms:   190.5785

这些数字每次运行都保持相当一致，@qwertyman 的方法总是比我的原始版本或@midjii 的方法快一点。它还有一个优点，就是它们中最干净、最好的，所以我要选择那个。

“Many HashSets”与“Single HashSet”如此接近让我感到有点惊讶，我原以为构建一百万个 HashSets 的开销会比大约 16 毫秒大(尽管这显然不算增加了垃圾收集器的压力)，尽管它们显然都远远落后于其他方法。

感谢您的帮助!

Answer 1

你可以这样做:

int n = 0;

// check if x0 is among the values in the second set
if (x0 == y0 || x0 == y1 || x0 == y2) {
    n++;
}

// check if x1 is among the values in the second set
if (x1 == y0 || x1 == y1 || x1 == y2) {
    n++;
}

// check if x2 is among the values in the second set
if (x2 == y0 || x2 == y1 || x2 == y2) {
    n++;
}

return n >= 2;

这依赖于(如您所述)每组中的数字不同的事实，从而使逻辑更简单。

---

如果你使用的是 C，你可以把它写得更短:

int n = 0;

n += x0 == y0 || x0 == y1 || x0 == y2;
n += x1 == y0 || x1 == y1 || x1 == y2;
n += x2 == y0 || x2 == y1 || x2 == y2;

return n >= 2;