給定一個數組找到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個奇數的子數組的數量？

回答

相關問題