spoj ARRAYSUB：O（n）的复杂性方法 [英] spoj ARRAYSUB: O(n) Complexity Approach
问题描述
我试图来解决这个问题上spoj http://spoj.pl/problems/ARRAYSUB
我解决了它使用两种方法
首先使用优化的蛮力。 其次以枢轴日K，2K，3K等，并发现最大的。
虽然这两个解决方案都接受最坏的情况下有复杂度为O（N * K）;
任何人都可以提出O（n）的解决方案途径的问题。
下面是我的跑步接受$ C $最坏情况下的复杂度为O的C（N * K）：
＃包括＆LT;的iostream＆GT;
＃包括＆LT; cstdio＆GT;
＃包括＆LT; climits＆GT;
使用名字空间std;
主要（）
{
N久;
CIN＆GT;＆GT; N;
长*改编=新长[N];
为（长I = 0;我n种;我++）
CIN＆GT;＆GT;改编[I]
长K表;
CIN＆GT;＆GT; K表;
长最大值= ARR [0];
为（长I = 1; I＆LT; k;我++）
{
如果（改编[I]≥最大）
最大= ARR [I]
}
如果（K！= N）
COUT＆LT;＆LT; MAX＆LT;＆LT;;
否则COUT＆LT;＆LT;最大;
为（长我= K，我n种;我++）
{
如果（ARR [I-K] ==最大值）
{最大值= -1;
为（中间体J =-K + 1; J＆其中; = I; J ++）
如果（ARR [J] GT;最大）
最大= ARR [J]。
如果（我！= N）
COUT＆LT;＆LT; MAX＆LT;＆LT;;
否则COUT＆LT;＆LT;最大;
}
其他{
如果（改编[I]≥最大）
{最大值=改编[I]
如果（我！= N）
COUT＆LT;＆LT; MAX＆LT;＆LT;;
其他
COUT＆LT;＆LT;最大;
}
其他
{
如果（我！= N）
COUT＆LT;＆LT; MAX＆LT;＆LT;;
否则COUT＆LT;＆LT;最大;}
}
}
COUT＆LT;＆LT; ENDL;
回报（0）;
}
中的数据结构，可以用来解决在O（n）的这个问题时是双端队列
大多数人会想到一个自然的方法是尽量保持队列大小一样的窗口的大小。尝试摆脱这一思想，并尽量想框外。除去冗余元件和存储只需要在队列被认为元件是实现高效的为O（n）以下的溶液的关键
无效maxInWindow（矢量＆lt; INT＆GT;＆安培; A，整数N，INT K，矢量＆lt; INT＆GT;和B）{
双端队列＆LT; INT＆GT; Q;
的for（int i = 0; I＆LT; k;我++）{
而（Q.empty（）及！＆安培; A [1]＆GT; = A [Q.back（）]）
Q.pop_back（）;
Q.push_back（ⅰ）;
}
对于（INT I = K，我n种;我++）{
B〔I-K] = A [Q.front（）];
而（Q.empty（）及！＆安培; A [1]＆GT; = A [Q.back（）]）
Q.pop_back（）;
而（Q.empty（）及！＆安培; Q.front（）＆其中; = I-k）的
Q.pop_front（）;
Q.push_back（ⅰ）;
}
B〔N-K] = A [Q.front（）];
// B存储每个连续的子阵大小为k的最大
}
说明：
第一个for循环计算第一数k的元素的最大和索引存储在Q.front（）。这将成为B [0] = A [指数]。 接下来的部分，我们的推从后面弹出，如果A [1]大于存储在previous最大。 我们的从前流行如果该指数的值小于IK，这意味着它不再是相关的。
I was trying to solve this problems on spoj http://spoj.pl/problems/ARRAYSUB
I solved it using two approaches
firstly using optimised brute force. Secondly taking Pivot at k,2k,3k so on and finding maximum.
Although both Solutions are accepted in worst case there Complexity are O(n*k);
Can anyone Suggest O(n) solution Approach for the problems .
Below is my Running Accepted code of worst case complexity O(n*k):
#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
main()
{
long n;
cin >> n;
long *arr = new long[n];
for( long i=0;i<n;i++)
cin >> arr[i];
long k;
cin >> k;
long max=arr[0];
for(long i=1;i<k;i++)
{
if(arr[i]>max)
max=arr[i];
}
if(k!=n)
cout<<max<<" ";
else cout<<max;
for( long i=k;i<n;i++)
{
if(arr[i-k]==max)
{max=-1;
for(int j=i-k+1;j<=i;j++)
if(arr[j]>max)
max=arr[j];
if(i!=n)
cout<<max<<" ";
else cout<<max;
}
else{
if(arr[i]>max)
{ max=arr[i];
if(i!=n)
cout<<max<<" ";
else
cout<<max;
}
else
{
if(i!=n)
cout<<max<<" ";
else cout<<max;}
}
}
cout<<endl;
return(0);
}
The data structure to be used to solve this problem in O(n) time is "deque"
A natural way most people would think is to try to maintain the queue size the same as the window’s size. Try to break away from this thought and try to think outside of the box. Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.
void maxInWindow(vector<int> &A, int n, int k, vector<int> &B) {
deque<int> Q;
for (int i = 0; i < k; i++) {
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = k; i < n; i++) {
B[i-k] = A[Q.front()];
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
while (!Q.empty() && Q.front() <= i-k)
Q.pop_front();
Q.push_back(i);
}
B[n-k] = A[Q.front()];
//B stores the maximum of every contiguous sub-array of size k
}
Explanation :
The first for loop calculates the maximum of the first 'k' elements and store the index at Q.front(). This becomes B[0] = A[index]. The next section, we push and pop from the back if A[i] is greater than the previous maximum stored. We pop from front if the value of the index is less than i-k which means it is no more relevant.
这篇关于spoj ARRAYSUB：O（n）的复杂性方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
