4

我有一个锯齿状的字符串数组，我需要找到所有唯一的行。例如，

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

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

4

4 回答 4

2

首先，作为数组，第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;
    }

}
于 2012-12-26T23:05:34.313 回答
2

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

您可以实现自定义IEqualityComparer<String[]>并Enumerable.GroupBy仅选择唯一的数组（group-count==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();
于 2012-12-26T23:18:16.527 回答
1

就算法解决方案而言，我会

  1. 对你的行进行排序（你可以使用任何你喜欢的排序指标，只要它能区分任何 2 个不同的行。）
  2. 选择没有相同相邻行的行。

如果这样做，您应该能够在O(m*n*lg(n))中完成您的要求， 其中m是行的长度，n是行数

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

于 2012-12-26T22:33:13.183 回答
0

我将按如下方式计算每一行的哈希：

[ 
 ["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 的方式如下，每行创建 hashset，然后找到一行与其他行的差异，如果差异为空，则它们是相同的。

您也可以使用交集，如果交集不为空，则该行不是唯一的。

于 2012-12-26T23:14:27.303 回答