我是C#的新手,我正在努力学习这门语言.

你能不能给我一个提示,我可以比较一个数组与从中选择最低值的数值？

喜欢：

Double[] w = { 1000,2000,3000,4000,5000 };

double min = double.MaxValue;
double max = double.MinValue;

foreach (double value in w)
{
    if (value < min)
        min = value;
    if (value > max)
        max = value;
}

Console.WriteLine(" min:",min);

给我w的最低值,我现在该如何比较？

如果我有：

int p = 1001 + 2000;  // 3001

我现在如何与数组列表进行比较,发现(3000)值是我的“Searchvalue”的最接近的值？

你可以用一些简单的数学来做到这一点,并且有不同的方法.

LINQ

Double searchValue = ...;

Double nearest = w.Select(p => new { Value = p,Difference = Math.Abs(p - searchValue) })
                  .OrderBy(p => p.Difference)
                  .First().Value;

手动

Double[] w = { 1000,5000 };

Double searchValue = 3001;
Double currentNearest = w[0];
Double currentDifference = Math.Abs(currentNearest - searchValue);

for (int i = 1; i < w.Length; i++)
{
    Double diff = Math.Abs(w[i] - searchValue);
    if (diff < currentDifference)
    {
        currentDifference = diff;
        currentNearest = w[i];
    }
}

我正面临一个问题,我想编写一个算法,可以在更大的数组中返回k个元素的每个连续子数组的max元素,并将这些max元素读入自己的数组,如下所示：

Given int array = {3,7,20,6,12,2,99,5,16},and int k = 4,--> creates the array {20,99} 
[because there are 7 consecutive sub-arrays of size 4 within the given array:
{3,6},{7,12},{20,2},...,{0,16}
and the max element of these,respectively,is 20,99 which 
are read into the resulting array.

现在这是我的问题：我知道如何在O(n ^ 2)复杂度中实现它,但是想要使它更快,使得它可以是O(n),或者如果不可能,那么O(nlog(n)) .有没有人知道是否有更快的方法来做到这一点,如果是这样,怎么样？

首先,朴素算法的复杂度是O(k(n-k 1))(通常这近似为O(k.n)),而不是O(n ^ 2).对于每个连续的子阵列(可能为n-k 1),您必须执行k比较.

你可以通过一些记忆来做得更好,使用一个长度为k的附加数组,我们可以称之为最大值.该数组将存储下一个最大值的索引.

对于数据集的每次迭代,都要检查最大值的第一个元素.您删除任何“过期”索引,现在第一个元素是您当前迭代的答案.

在数据中滑动窗口(大小为k)时,将当前索引推送到最大值,然后按如下方式修剪：索引最大值[i]的值必须小于索引最大值[i-1]的值.如果不是,那么你继续将索引冒泡到最大值的开头,一次一个点,直到这变为真.

实际上,最好将maximums数组视为环形缓冲区.修剪过程将尾部缩回头部,同时弹出任何“过期”的最大值(当窗口滑过它们时)将使头部前进一步.

它有点笨重,但这里有一些工作代码来说明：

#include <vector>
#include <iostream>

int main()
{
    const int window_size = 4;
    std::vector<int> vals = { 3,16 };
    std::vector<int> maximums( window_size );
    int mhead = 0,mtail = 0;

    for( int i = 1; i < vals.size(); i ++ )
    {
        // Clean out expired maximum.
        if( maximums[mhead] + window_size <= i )
        {
            int next_mhead = (mhead + 1) % window_size;
            if( mtail == mhead ) mtail = next_mhead;
            mhead = next_mhead;
        }

        if( vals[i] >= vals[ maximums[mtail] ] )
        {
            // Replace and bubble up a new maximum value.
            maximums[mtail] = i;
            while( mhead != mtail && vals[ maximums[mtail] ] >= vals[ maximums[(mtail+window_size-1)%window_size] ] )
            {
                int prev_mtail = (mtail + window_size - 1) % window_size;
                maximums[prev_mtail] = maximums[mtail];
                mtail = prev_mtail;
            }
        }
        else
        {
            // Add a new non-maximum.
            mtail = (mtail + 1) % window_size;
            maximums[mtail] = i;
        }

        // Output current maximum.
        if( i >= window_size - 1 )
        {
            std::cout << vals[ maximums[mhead] ] << " ";
        }
    }

    std::cout << std::endl;
    return 0;
}

现在,时间复杂度……

最好的情况是O(n),如果您的所有数据都已排序(升序或降序),则会发生这种情况.

我认为最坏的情况是O(2n).在一次迭代中需要k个额外操作的唯一方法是,如果已经有k步线性复杂度(以便环形缓冲区已满).在这种情况下,环形缓冲区将为空以进行下一步.由于我们只能填充和清空环形缓冲区n / k次,因此偶然的k运算出现在k.n / k或n.

你应该能够证明,即使不断地部分清空环形缓冲区也会导致相同的复杂性.

最后,我们可以结束并调用整个O(n),因为任何常数因子对于大n都是无关紧要的.它实际上比我预期的要好. =)