获取数组中最频繁和最相似值的最快方法

本文关键字：方法 相似 数组 获取 | 更新日期: 2023-09-27 18:28:31

我在C#中有一个int数组，我想得到整个数组的5%，就像新数组包含最频繁的相似值一样。举个例子，假设我有一个包含100个条目的数组，其中包括40个20（15到25）的兄弟。我想要的是将20作为最频繁的值（包括它的兄弟值）检测为一个新数组，然后检测新数组中的5个最频繁值。我需要在ASP.net网站上运行代码，因此，我需要一个快速算法。有人能帮我吗？

获取数组中最频繁和最相似值的最快方法

您可以构建一个简单的算法，方法是对值进行分组，按计数排序，然后取它们，直到填充所需的5%数组，如下所示：

// Build a set of {Value, Count} pairs using LINQ
var counts = data
    .GroupBy(v => v)
    .Select(g => new {
        Value = g => Key
    ,   Count = g.Count()
    }).OrderByDescending(p => p.Count)
    .Take(5);

编辑：

阵列的大小可以大到1024*1024，并且范围在0和255 之间

由于范围很小，您可以使用计数数组而不是一个组，如下所示：

int counts = new int[256];
foreach (var b in data) {
    counts[b]++;
}

现在，您可以运行快速选择算法来选择第五项。以下是提供QuickSelect的C#实现的答案。

var fifth = QuickSelect(counts, 5);
var res = new List<KeyValuePair<int,int>>();
for (int i = 0 ; i != counts.Length && res.Length != 5 ; i++) {
    if (counts[i] >= fifth) {
        res.Add(new KeyValuePair<int,int>(i, counts[i]));
    }
}

您可能需要将快速选择算法替换为中值算法，该算法具有相同的线性性能，但不是随机化的。

var numbersByOccurrence = from numbers in yourNumberArrayVariable
                          group numbers by numbers into g
                          select new { Number = g.Key, Count = g.Count() };
var limitedSize = numbersByOccurrence.OrderByDescending(n => n.Count).Take(5);

现在，您有一个由5个对象组成的变量（可以强制转换为数组或列表），其中包含一个可以轻松访问的Number和Count变量。

相关文章：