给定一个数组找到m个奇数的子数组的数量？

样品输入： 1 2 3 4 5（数组元素） m = 1（奇数）示例输出： 8。子阵列是[[1]，[1,2]，[2,3]，[2,3,4]，[3]，[3,4]，[4,5]，[5]]给定一个数组找到m个奇数的子数组的数量？

这是我的implementation.In最坏的情况下，这将需要O（N + N^2）.Are有任何优化此代码的方法？

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; 
}

来源

2017-08-12 Sanjeevkumar M Snj

正如兴趣点，大O表示法往往只用最显著项，因此你的算法会为O（n^2）。 – paxdiablo

这可以在O(n)中解决。首先生成奇数之间的间隙长度数组，将两端计数为隐式奇数。在这种情况下，该数组是g = [0,1,1,0]。然后我们总计(g[i]+1)*(g[i+m]+1)，因为它表示有多少个子阵列在第奇数处开始，或者在第奇数处开始，或者在奇数处结束，或者在第奇数处结束或紧接在第i+m处开始。

在这种情况下，我们得到1*2 + 2*2 + 2*1 = 8。

来源

2017-08-12 02:00:03 btilly

是啊...我明白了。 –

你可以很容易地得到O（n log n）。你的代码的一个简单的改进是在你的内循环（在j）上，而不是一个接一个地计算你在区间[i，n]上进行二分搜索以找到导致m个奇数的第一个位置，和第一个导致m + 1个奇数的位置;然后减去它们。

但是，要做到这一点，您需要有一个sum []数组，其中第i个位置显示区间[0，i]中的奇数个数。这可以在O（n）中预先计算一个for循环。

现在，您在您的二进制搜索使用这样的：

for(int i = 0; i < n; i++){ 
    int lo = i; 
    int hi = n; 

    while(lo < hi){ 
     int mid = (lo + hi)/2; 
     int count = sum[mid]; 
     if(i > 0) count -= sum[i - 1]; 

     //count shows number of odd in the interval [i, mid] 
     if(mid >= m){ 
      hi = mid; 
     } 
     else{ 
      lo = mid + 1; 
     } 
    } 

    int first_with_m = lo; 

    //do another binary search to find first_with_m_plus_one 

    answer += first_with_m_plus_one - first_with_m; 
}

来源

2017-08-12 05:41:42

给定一个数组找到m个奇数的子数组的数量？

回答

相关问题