0

是否有任何算法可以从给定的成对数列表中找到未成对数。例如在 {(1,2),(2,3),(3,4)} 对 (1,3) 和 (2,4 ) 从未配对。

4

2 回答 2

4

你可以这样做:

  1. 遍历所有对并建立一组出现在集合中的所有数字。
  2. 构造所有可能的数字对,将结果存储在不同的集合中。
  3. 遍历原始列表中的所有对,并从所有对的集合中删除您找到的每一对。
  4. 您现在剩下所有未出现在原始集合中的对。

当然,这假设您只关心原始集合中的值对。例如,对 (1, 5) 也不在您的示例中。(猫,狗)也不是。

这在时间 O(n 2 ) 中运行,其中 n 是原始对集中表示的数字的数量。

希望这可以帮助!

于 2012-08-27T17:26:30.377 回答
0

使用 LINQ 和对称技巧,利用 (1,3) 和 (3,1) 相同的事实,因此忽略第二个数字大于第一个数字的情况:

public static IEnumerable<Tuple<int, int>> GetUnpairedNumbers(IEnumerable<Tuple<int, int>> existingPairs ) {
    var uniqueNumbers = existingPairs.SelectMany(p => new[] {p.Item1, p.Item2}).Distinct().ToList();
    var isUsed = uniqueNumbers.ToDictionary(n => n, n => uniqueNumbers.Where(inner => n < inner).ToDictionary(inner => inner, inner => false));

    foreach(var currentPair in existingPairs) {
        isUsed[currentPair.Item1][currentPair.Item2] = true;
    }

    return isUsed.Keys.SelectMany(n => isUsed[n].Where(kvp => !kvp.Value).Select(kvp => Tuple.Create(n, kvp.Key)));
}
public static void Main(string[] args) {
    var unpairedNumbers = GetUnpairedNumbers(new[] { P(1, 2), P(2, 3), P(3, 4) });
}

private static Tuple<int, int> P(int a, int b) {
    return Tuple.Create(a, b);
}
于 2012-08-27T18:03:56.147 回答