数组之间搜索的最佳算法

Question

我有一个问题需要用我能找到的最好的算法来解决。
让我先描述一下这个问题。我有一个类A，有Hashset<int>的个数，有Z的个数

A -> {x,y,z | x = {0,1,2} , y = {-1,0,9} ... }
B -> {x,y,z,k | x = {0,1,-2} , y = {-1,0,19} ... }

…

输入一个新的数组int{…}，结果应该是哈希集最多的组，输入和组之间的数字匹配。

例如:

A : {[1,2,3][2,3,8][-1,-2,2]}  
B : {[0,-9,3][12,23,68][-11,-2,2]}

输入:

[2,3,-19]
result A : {[2,3][2,3][2]}  
result B : {[3][][2]}
A : 3  
B : 2

A是正确答案。

或者类似的东西。是的，我知道这是一个主观的问题，但这是一个很好的理由。

Answer 1

假设您有未知数量的样本要检查输入集，这个Linq查询应该可以做到。

from sample in samples
let intersectedSets =
  from set in sample
  let intersection = input.Intersect(set)
  where intersection.Count() > 0
  select intersection
orderby intersectedSets.Count() descending
select intersectedSets;

最上面的元素是你想要的样本，因此yourCollection.First()将产生你的结果集——在你给出的例子中:

var samples = new[] {
  new[]{
    new[]{1, 2, 3},
    new[]{2, 3, 8},
    new[]{-1, -2, 2}
  },
  new[]{
    new[]{0, -9, 3},
    new[]{12, 23, 68},
    new[]{-11, -2, 2}
  }
};
var input = new[]{2, 3, -19};
var result =
  (from sample in samples
  let intersectedSets =
    from set in sample
    let intersection = input.Intersect(set)
    where intersection.Count() > 0
    select intersection
  orderby intersectedSets.Count() descending
  select intersectedSets).First();
result.Dump(); // LINQPad extension method

Answer 2

显然你想用c#来实现这个。我不知道这是不是最好的算法(在任何情况下)，但你可以用LINQ把它写下来，非常简单明了:

        int[][] arrays = new[] { new[] { 1, 2 }, new[] { 2, 3 }, new[] {3, 4} };
        int[] input = new[] { 1, 4 };
        Console.WriteLine(arrays.Count((itemarray) => itemarray.Any((item) => input.Contains(item))));

在一个int数组数组中查找至少包含一个输入数组值的数组的个数。这就是你所做的，尽管我不确定这是否是你对我们的要求。

Answer 3

给定一个示例类HashHolder和它的实例A:

public class HashHolder
{
    public HashHolder()
    {
        Hashes = new List<HashSet<int>>();
    }
    public List<HashSet<int>> Hashes { get; set; }
}

您可以按hashset分组并取所有组之间的最大计数:

var maxHash = A.Hashes.GroupBy(h => h)
               .Select(g => new { Hash = g.Key, Count = input.Count(num => g.Key.Contains(num)) })
               .OrderByDescending(g => g.Count)
               .FirstOrDefault();

如果maxhHash不为空，则结果为maxHash.Hash。