C:找到子数组数组中的最大整数
我正面临一个问题,我想编写一个算法,可以在更大的数组中返回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都是无关紧要的.它实际上比我预期的要好. =) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |