加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

C:找到子数组数组中的最大整数

发布时间:2020-12-16 07:15:33 所属栏目:百科 来源:网络整理
导读:我正面临一个问题,我想编写一个算法,可以在更大的数组中返回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 con
我正面临一个问题,我想编写一个算法,可以在更大的数组中返回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都是无关紧要的.它实际上比我预期的要好. =)

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读