提高嵌套循环的性能

Question

该逻辑用于找到数组中的数字n,其中n和n + 5之间的范围将包括数组中的最多数字.我提出了一个解决方案,但它需要一个嵌套循环,因此它有点慢.有没有办法改善其表现？提前致谢.

数组保证排序.

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
int bestNumber = 0;
int MaxMatchFound = 0;

for (int o = 0; o < myArray.Length; o++)
{

    int TempMatchFound = 0;

    for (int i = 0; i < myArray.Length; i++)
    {
        if (myArray[i] >= myArray[o] && myArray[i] <= (myArray[o] + 5))
        {
            TempMatchFound++;
        }
    }
    if (TempMatchFound > MaxMatchFound)
    {
        bestNumber = myArray[o];
        MaxMatchFound = TempMatchFound;
    }

}

return bestNumber;

Answer 1

暂存值,然后遍历值v并对所有w满足的值的相关计数求和v <= w <= v + 5,然后找到最大计数:

var buckets = myArray.GroupBy(n => n)
                     .ToDictionary(g => g.Key, g => g.Count());
var rangeCounts = 
    buckets.Keys
           .Select(v =>
               new {
                   Value = v,
                   Count = Enumerable.Range(0, 6)
                                     .Sum(i => buckets.ContainsKey(v + i) ? 
                                               buckets[v + i] : 
                                               0
                                         )
               }
    );
var bestRange = rangeCounts.MaxBy(x => x.Count);

现在,bestRange.Value是最佳范围的起点,bestRange.Count是落入范围内的元素数量[bestRange.Value, bestRange.Value + 5].在这里,我用过MaxBy.

认为这可以让你获得线性表现.建筑字典是线性的,建筑范围是线性的,MaxBy是线性的.甚至适用于非分类.