c# - 在数组中获取最频繁和相似值的最快方法？

Question

我在 C# 中有一个整数数组，我想获得整个数组的 5%，新数组包含最频繁的相似值。例如，假设我有一个包含 100 个条目的数组，其中包括 40 个 20(15 到 25)的 sibling 。我想要的是将 20 作为最频繁的值(包括它的兄弟)检测为一个新数组，然后在新数组中检测 5 个最频繁的值。我需要在 ASP.net 网站上运行代码，因此，我需要一个快速算法。谁能帮我解决这个问题？

Answer 1

您可以构建一个简单的算法，方法是对值进行分组，按计数排序，然后获取它们直到填充所需的 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);

编辑:

The array may be as big as 1024*1024 in size and the ranges are between 0 and 255

由于范围很小，你可以使用计数数组代替组，像这样:

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

现在您可以运行 Quick Select Algorithm选择第五项。这是 an answer提供了 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]));
    }
}

您可能想用 median-of-medians algorithm 替换快速选择算法，具有相同的线性性能，但不是随机的。