4

给定一个列表列表（比如说 5个列表，有一个可以使用的实数），我可以使用以下代码的变体：

var list1 = new List<int>() { 1, 2, 3 };
var list2 = new List<int>() { 2, 3, 4 };
var list3 = new List<int>() { 3, 4, 5 };
var listOfLists = new List<List<int>>() { list1, list2, list3 };
var intersection = listOfLists.Aggregate((previousList, nextList) => previousList.Intersect(nextList).ToList());

现在假设intersection最终包含 0 个项目。很可能有一些对象是 4/5 列表共有的。我将如何以最有效的方式找到它们？

我知道我可以遍历 4 个列表的所有组合并保存所有结果，但是该方法不能很好地扩展（最终必须在大约 40 个列表上完成）。

如果 4 个列表没有共同的项目，则将重复搜索以寻找 3/5 列表共同的项目等。在视觉上，这可以由网格点列表表示，我们正在搜索具有最多的点重叠。

有任何想法吗？

编辑：也许最好查看每个点并跟踪它在每个列表中出现的次数，然后创建一个出现次数最多的点列表？

4

2 回答 2

6

您可以从所有列表中选择所有数字（点），并按值对它们进行分组。然后按组大小对结果进行排序（即列出点存在的位置）并选择最常见的项目：

var mostCommon = listOfLists.SelectMany(l => l)
                            .GroupBy(i => i)
                            .OrderByDescending(g => g.Count())
                            .Select(g => g.Key)
                            .First();
// outputs 3

First()您可以通过替换来获取几个最重要的项目，而不是只获取第一项Take(N)。

返回具有列表数量的项目（按列表数量排序）：

var mostCommonItems = from l in listOfLists
                      from i in l
                      group i by i into g
                      orderby g.Count() descending
                      select new {
                         Item = g.Key,
                         NumberOfLists = g.Count()
                      };

用法（item 是强类型匿名对象）：

var topItem = mostCommonItems.First();
var item = topItem.Item;
var listsCount = topItem.NumberOfLists;

foreach(var item in mostCommonItems.Take(3))
    // iterate over top three items
于 2013-07-17T15:16:54.117 回答
1

您可以先组合所有列表，然后使用字典策略找到列表的模式，如下所示。这使它非常快：

/// <summary>
/// Gets the element that occurs most frequently in the collection.
/// </summary>
/// <param name="list"></param>
/// <returns>Returns the element that occurs most frequently in the collection.
/// If all elements occur an equal number of times, a random element in
/// the collection will be returned.</returns>
public static T Mode<T>(this IEnumerable<T> list) 
{
    // Initialize the return value
    T mode = default(T);

    // Test for a null reference and an empty list
    if (list != null && list.Count() > 0)
    {
        // Store the number of occurences for each element
        Dictionary<T, int> counts = new Dictionary<T, int>();

        // Add one to the count for the occurence of a character
        foreach (T element in list)
        {
            if (counts.ContainsKey(element))
                counts[element]++;
            else
                counts.Add(element, 1);
        }

        // Loop through the counts of each element and find the 
        // element that occurred most often
        int max = 0;

        foreach (KeyValuePair<T, int> count in counts)
        {
            if (count.Value > max)
            {
                // Update the mode
                mode = count.Key;
                max = count.Value;
            }
        }
    }

    return mode;
}
于 2013-07-17T15:25:07.060 回答