從給定數字對發現不成對數字

Question

是否有任何算法從給定配對數字列表中找到不成對數字。例如，在{（1,2），（2,3），（3,4）}對中（1,3）和（2,4）從未配對過。

Answer 1

你能做到這一點，如下所示：

1. 遍歷所有對，並建立了一套都出現在一組的數字。
2. 構建所有可能的數字對，將結果存儲在不同的集合中。
3. 迭代原始列表中的所有對，並從所有對的集合中刪除找到的每個對。
4. 您現在剩下所有未出現在原始集合中的對。

當然，這假定你只關心原始集合中的值對。例如，對（1,5）也不在你的例子中。 （貓，狗）都不是。

這運行在時間O（n ），其中n是在原始組對中表示的數字的數量。

希望這會有所幫助！

Answer 2

使用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); 
}