1

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

4

2 回答 2

3

您可以通过对值进行分组、按计数排序、然后将它们取到填充所需的 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]++;
}

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

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]));
    }
}

您可能想用中位数算法替换快速选择算法，该算法具有相同的线性性能，但不是随机的。

于 2013-08-20T17:14:21.310 回答
2 
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 变量。

于 2013-08-20T17:14:35.220 回答