获取开始索引和结束索引之间的数组最大值和最小值

我需要一个简单，轻量级的方法来获得双精度数组的max和min值的想法。技巧是我只需要数组中两个索引之间的最大值和最小值。

内置的arrayOfDoubles.Max()和arrayOfDoubles.Min()将不工作，因为它们检查整个数组。

这段代码将持续运行，需要有一定的效率。也就是说，的简单性和可读性比速度本身更重要。

下面是获取两个索引之间最大和最小值的一种方法:

double[] array = new double[8] { 3, 1, 15, 5, 11, 9, 13, 7 };
int startIndex = 3;
int endIndex = 6;
// Get max and min between these two indexes in the array
double max = GetMax(array, startIndex, endIndex);
double min = GetMin(array, startIndex, endIndex);
Console.WriteLine("Max = " + max + ", Min = " + min);

GetMax和GetMin的代码非常相似:

private static double GetMax(double[] array, int startIndex, int endIndex)
{
    double max = double.MinValue;
    for (int i = startIndex; i <= endIndex; i++)
    {
        // Increase max with each bigger value
        max = Math.Max(max, array[i]);
    }
    return max;
}

输出:Max = 13, Min = 5

问题:我还有什么方法可以得到同样的结果，可能更简单，不需要太多的开销?

var list = array.Skip(startIndex).Take(endIndex - startIndex + 1).ToList();
var min = list.Min();
var max = list.Max();

您还可以:

var segment = new ArraySegment<double>(array, startIndex, endIndex - startIndex + 1);
var min = segment.Min();
var max = segment.Max();

很明显，在未排序的数组中查找最小和最大元素需要O(n)算法，因为无论如何都必须检查每个元素，至少检查一次。因此，您唯一可以期望的优化是特定于实现的，并且只能在常量方面为您带来收益。

然而，有一个聪明的技巧，你可以使用3*[n/2]比较来找到数组中的最小值和最大值。虽然这不是渐进的改进，但与直接算法中需要的典型的2*n比较相比，它是n/2的改进。因此，如果你希望执行大量的最小/最大计算，那么它可能值得考虑作为一个选项。

你可以这样做:

在两个变量
在每次迭代时:
- 比较下两个元素，以确定哪一个更大
- 将较大的元素与最大值进行比较(必要时交换)
- 将较小的元素与最小元素进行比较(必要时交换)

你将执行n/2次循环，每次迭代3次比较，总共3*[n/2]次操作。

下面是一个实现:

void GetMinMax(double[] array, int start, int end, out double min, out double max)
{
    min = array[start];
    max = array[start];
    if((end - start) % 2 == 0)               // if there's an odd number of elements
       start = start + 1;                    //   skip the first one
    for (int i = start + 1; i <= end; i += 2)
    {
        if(array[i] > array[i-1])
        {
            if(array[i] > max) max = array[i];
            if(array[i - 1] < min) min = array[i - 1];
        } else {
            if(array[i - 1] > max) max = array[i - 1];
            if(array[i] < min) min = array[i];
        }
    }
}

可以扫描数组一次。这是标准的最小/最大跟踪算法，在无数的面试问题中都会被问到，所以可读性不应该是一个问题。

void GetMinMax(double[] array, int start, int end, out double min, out double max)
{
    min = Double.MaxValue;
    max = Double.MinValue;
    // TODO: error checks for out-of-bounds, null, etc...
    for (int i = start; i <= end; ++i)
    {
        if (array[i] > max) max = array[i];
        if (array[i] < min) min = array[i];
    }
}

编辑:

使用Usman Zafar的答案来简化和消除对几个错误检查的需要:

void GetMinMax(IList<double> list, out double min, out double max)
{
    // TODO: null/empty check for list.
    min = Double.MaxValue;
    max = Double.MinValue;
    for (int i = 0; i < list.Count; ++i)
    {
        if (list[i] > max) max = list[i];
        if (list[i] < min) min = list[i];
    }
}

现在呼叫任何IList<double>，或者在您的情况下:new ArraySegment<double>(array, 3, 4)。

使用的甜药是LINQ:

        var res = array.Skip(startIndex).Take(1 + endIndex - startIndex );
        var min = res.Min();
        var max = res.Max();

相关内容

最新更新

热门标签：