0

此逻辑是在数组中查找数字 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;
4

4 回答 4

5

存储这些值，然后遍历这些值并对满足v的所有值的相关计数求和，然后找到最大计数：wv <= 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.

认为这可以获得线性性能。构建字典是线性的，构建 rangeCounts 是线性的，MaxBy是线性的。甚至适用于非排序。

于 2013-06-10T21:11:43.370 回答
4

给你：这在 O(N) 时间和 O(1) 内存中运行。这形成了其他解决方案中描述的存储桶，然后在您通过阵列时丢弃它们。队列用于跟踪哪些桶是“活动的”，因为它们可以被添加到。字典中的条目永远不会超过 6 个，队列也不会。

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
Dictionary<int, int> counts = new Dictionary<int, int>();
Queue<int> q = new Queue<int>();

int n = 0;
int currentMaxCount = 0;


for(int i = 0; i < myArray.Length; i++)
{
    var currentNum = myArray[i];
    if(counts.ContainsKey(currentNum))
    {
        counts[currentNum]++;
    }
    else
    {
        counts[currentNum] = 1;
        q.Enqueue(currentNum);
    }

    for(int j = 1; j <= 5; j++)
    {
        if(counts.ContainsKey(currentNum - j))
            counts[currentNum - j]++;
    }

    if(q.Peek() + 5 < currentNum)
    {
        if(counts[q.Peek()] > currentMaxCount)
        {
            currentMaxCount = counts[q.Peek()];
            n = q.Peek();
        }
        counts.Remove(q.Dequeue());

    }
}

while(q.Count > 0)
{
    if(counts[q.Peek()] > currentMaxCount)
    {
        currentMaxCount = counts[q.Peek()];
        n = q.Peek();
    }
    counts.Remove(q.Dequeue());
}

Console.WriteLine("There are {0} matches between {1} and {2}", currentMaxCount, n, n + 5);
于 2013-06-10T21:10:34.913 回答
3

这是一个 O(n) 的解决方案，无论范围如何，都使用 O(1) 额外空间。

它只通过数组一次，总是进行 2N 次比较。我看不出有什么方法可以改进这个算法，尽管肯定有一些微优化可以从实现中挤出一点速度。

private int FindRange(int[] myArray)
{
    const int range = 5;
    int start = 0;
    int maxMatchFound = 0;
    int maxIndex = 0;
    for (int i = 0; i < myArray.Length; ++i)
    {
        if (myArray[i] > myArray[start] + range)
        {
            int matchLength = i - start;
            if (matchLength > maxMatchFound)
            {
                maxMatchFound = matchLength;
                maxIndex = start;
            }
            // move forward until within range
            do
            {
                ++start;
            } while (myArray[i] > myArray[start] + range);
        }
    }
    // Final check, from myArray[start] to end of array
    int len = myArray.Length - start;
    if (len > maxMatchFound)
    {
        maxMatchFound = len;
        maxIndex = start;
    }
    return maxIndex;

这里的想法是，如果一个特定的数字a[x]落在范围内，a[i]那么它将落在范围内a[i+1]，假设x > i。（因此在您的原始数组中， at 的值在a[3]的范围内，因此它也将在anda[0]的范围内）。a[1]a[2]

因此索引i会递增，直到它引用的值超出a[start]. 然后，start递增，直到a[i]再次在范围内。这两个索引以交替的方式在数组中向前移动。

于 2013-06-10T21:47:33.433 回答
0

这是一个单行 LINQ 选项。在性能方面不是最好的（它迭代多次）。还是值得注意的。

var result = myArray
             .OrderByDescending(i => myArray.Count(i2 => i2 >= i && i2 <= i + 5))
             .First();
于 2013-06-10T20:56:02.240 回答