样本输入：
1 2 3 4 5(数组元素)
m = 1(奇数)
样本输出：
8.
子阵列是[[1],[1,2],[2,3],3,4],[3],[3,[4,5],[5]]
1 2 3 4 5(数组元素)
m = 1(奇数)
样本输出：
8.
子阵列是[[1],[1,2],[2,3],3,4],[3],[3,[4,5],[5]]
这是我的实现.在最坏的情况下,它需要O(n n ^ 2).是否有任何方法来优化此代码？
- int main() {
- int n,*a,count1=0,m,*dp;
- cin>>n;
- a = new int[n];
- dp =new int[n];
- for(int i=0; i<n; i++) {
- cin >> a[i];
- }
- cin >> m;
- for(int i=0; i<n; i++){
- if(a[i]%2==1) {
- count1++;
- }
- dp[i] =count1;
- }
- int prev;
- long count=0;
- for(int i=0; i<n; i++) {
- prev= i==0 ? 0:dp[i-1];
- for(int j=i; j<n; j++) {
- if((dp[j] - prev) == m){
- count++;
- }
- if(dp[j] - prev > m){
- break;
- }
- }
- }
- cout<<count;
- }
解决方法
这可以在O(n)中解决.首先生成奇数之间的间隙长度的数组,将两端计为隐式奇数.在这种情况下,该数组是g = [0,1,0].然后我们求和(g [i] 1)*(g [i m] 1)因为它表示有多少子阵列在第i个奇数开始或恰好在第i个奇数之前,并且在第i个奇数之后或之后结束.
在这种情况下,我们得到1 * 2 2 * 2 2 * 1 = 8.
替代解释
想想想要的子阵列.每个人都从某处开始,包括m个奇数,然后在其他地方结束.让我们根据它们包含的奇数字串将它们分成组.每个组包含一些i的第i个奇数,并且以第m-1个奇数结束.起点在第i-1和第i个奇数之间的每个偶数处,以及第i个奇数本身.这是第i个奇数1之前的间隙的大小.或者在我的计算中g(i)1.类似地,结束点位于第m-1个奇数处,或者在该第i个奇数之间的所有均匀处.这是i m-1和i mth奇数之间差距的1倍.在我的计算中,g(i m)为1.因此,该组中的数字是起点数乘以结束点数.其中(g(i)1)*(g(i m)1).在所有起点上添加我,我们得到了答案.
我掩饰了一个重要的细节.这是我假设包含奇数,所以0<米如果m = 0,则计算完全改变.然后答案是1和(g(i)*(g(i)-1)/ 2).
