查找锯齿状阵列的独特行

Question

我有一个锯齿状的字符串阵列，我需要找到所有独特的行。例如，对于例如

[ 
["A","B"] , 
["C","D","E"], 
["B", "A"], 
["E","A"] 
] 

这应该返回行1和行3作为行0和行2是重复的。如何才能做到这一点？我可以使用hashets吗？

Answer 1

首先，作为数组，行0和行2不重复。他们只有一套相同的元素。但是，如果你只是想删除这些样行，你可以这样做：

string[][] GetNonDuplicates(string[][] jagged) 
{ 
    //not a hashset, but a dictionary. A value of false means that the row 
    //is not duplicate, a value of true means that at least one dulicate was found 
    Dictionary<string[], bool> dict = 
      new Dictionary<string[], bool>(new RowEqualityComparer()); 

    foreach(string[] row in jagged) 
    { 
    //if a duplicate is found - using the hash and the compare method 
    if (dict.ContainsKey(row)) 
    { 
     dict[row] = true; //set value to true 
    } 
    else 
    { 
     dict.Add(row, false); //first time we see this row, add it 
    } 
    } 

    //just pop out all the keys which have a value of false 
    string[][] result = dict.Where(item => !item.Value) 
          .Select(item => item.Key) 
          .ToArray(); 
    return result; 
} 

... 
string[][] jagged = new []{new []{"A","B"} , 
          new []{"C","D","E"}, 
          new []{"B", "A"}, 
          new []{"E","A"}}; 

string[][] nonDuplicates = GetNonDuplicates(jagged); 

其中RowEqualityComparer是：

class RowEqualityComparer : IEqualityComparer<string[]> 
{ 
    public bool Equals(string[] first, string[] second) 
    { 
     // different legths - different rows 
     if (first.Length != second.Length) 
      return false; 

     //we need to copy the arrays because Array.Sort 
     //will change the original rows 
     var flist = first.ToList(); 
     flist.Sort(); 
     var slist = second.ToList(); 
     slist.Sort(); 

     //loop and compare one by one 
     for (int i=0; i < flist.Count; i++) 
     { 
      if (flist[i]!=slist[i]) 
       return false; 
     } 
     return true; 
    } 

    public int GetHashCode(string[] row) 
    { 
     //I have no idea what I'm doing, just some generic hash code calculation 
     if (row.Length == 0) 
     return 0; 
     int hash = row[0].GetHashCode(); 
     for (int i = 1; i < row.Length; i++) 
     hash ^= row[i].GetHashCode(); 
     return hash; 
    } 

} 

Answer 2

至于算法解去，我倒是

1. 排序的行（你可以使用任何排序指标你喜欢，只要它区别于任何两个不同行。）
2. 挑行没有相同的相邻行。

如果你这样做，你应该能够完成O（m * n个* LG电子（n））的其中米是你行的长度，ñ是您的要求行数

鉴于值集意味着相等，您可以对每行的单元格进行排序以帮助您对行列表进行排序。这将导致O（n * m * lg（m）+ m * n * lg（n））

Answer 3

我会计算每行的哈希值如下：

[ 
["A","B"] , // hash of this row :10 as example 
["C","D","E"], // hash of this row : 20 
["B", "A"], // hash of this row would be 10 as well 
["E","A"] 
] 

因为它们都是字符串，所以可以计算哈希值并为每行创建一个哈希值。

您可以使用HashSet的方式如下，每行创建一个哈希集，然后找到每行其他行的差异，如果差异是空的，那么它们是相同的。

也可以使用交点，如果交点不为空，那么该行不是唯一的。

Answer 4

假设您想忽略顺序，重复项（因为您已经提到了HashSet），并且结果应该只包含没有重复项的数组。

您可以实现自定义IEqualityComparer<String[]>为Enumerable.GroupBy并仅选择都有它独特阵列（组数== 1）：

class IgnoreOrderComparer : IEqualityComparer<string[]> 
{ 
    public bool Equals(string[] x, string[] y) 
    { 
     if (x == null || y == null) return false; 
     return !x.Distinct().Except(y.Distinct()).Any(); 
    } 

    public int GetHashCode(string[] arr) 
    { 
     if (arr == null) return int.MinValue; 
     int hash = 19; 
     foreach (string s in arr.Distinct()) 
     { 
      hash = hash + s.GetHashCode(); 
     } 
     return hash; 
    } 
} 

其余部分很简单：

String[][] uniques = arrays.GroupBy(arr => arr, new IgnoreOrderComparer()) 
          .Where(g => g.Count() == 1) 
          .Select(g => g.First()) 
          .ToArray(); 

编辑 ：下面是使用同一比较器的可能更高效的版本：

IEqualityComparer<string[]> comparer = new IgnoreOrderComparer(); 
String[][] uniques = arrays.Where(a1 => 
    !arrays.Any(a2 => a1 != a2 && comparer.Equals(a1, a2))) 
          .ToArray();