如何減少計算O（N）有界切片數的時間複雜度？

給出了整數K和由N整數組成的非空零索引數組A。一對整數（P，Q），使得0 ≤ P ≤ Q < N被稱爲陣列A的切片。如何減少計算O（N）有界切片數的時間複雜度？

Bounded_slice是切片，其中切片中的最大值和最小值之間的差小於或等於到K.更準確地說，它是一個切片，例如max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K。目標是計算有界數量。

我的解決方案如下：

int solution(int K, int A[], int N){ 

    // write your code in C90 
    int p, q, max, min, bndSlice = N; 

    for(p = 0; p < (N - 1); p++){ 
     for(q = (p + 1); q < N; q++){ 
      MaxMinSlice(A, p, q, &max, &min); 

      if((max - min) <= K){ 
       bndSlice++; 
      } 

      if(bndSlice > 1000000000){ 
       return 1000000000; 
      } 
     } 
    }   
    return bndSlice; 
} 
void MaxMinSlice(int A[], int p, int q, int *max, int *min){ 

    int i;   
    *max = *min = A[p]; 

    for(i = p; i <= q; i++){ 
     if(*max < A[i]){ 
      *max = A[i]; 
     } 

     if(*min > A[i]){ 
      *min = A[i]; 
     } 
    } 
}

如何減少上面的代碼的時間複雜度爲O（N）？

來源

2014-01-23 user3227784

我已發佈O（N）的答案在同一個問題在http://stackoverflow.com/questions/21251707） –

可能重複的[計數綁定編切片codility]（http://stackoverflow.com/questions/21251707/counting-bounded-slice-codility） –

小更正：爲（P = 0; p

你的代碼是O（n^3）。有一種更簡單的方法來製作它O(n^2 * log n)。使用Range Minimum Query（RMQ）對數組進行預處理，以便MaxMinSlice（）需要O（1）查詢給定的最大值和最小值（p，q）的差值。

RMQ是O（n * logn）。所以總時間是O（n * log n）+ O（n^2）

來源

2014-01-23 13:03:26

允許有界重疊嗎？我懷疑在這種情況下可能會低於O（N^2）（假設所有數組元素的平凡情況相同，這意味着每個可能的切片都是有界的，這意味着您得到一組切片，其中N^2 ，這將表明O（N^2）複雜性）。

如果bounded_slices不允許重疊：

集P = Q = 1。設置min = max = A [P]。增加Q，調整最小值和最大值到A [Q]，直到（最大 - 最小）> K。然後，[P..Q-1]是一個有界的切片。設置P = Q並從開始重複，直到達到N.這需要O（N）操作。

如果允許有界切片重疊，在上述算法中，當您找到有界切片時，設置P = P + 1而不是P = Q。但是這需要O（N^2）操作。

來源

2014-01-23 13:08:34

問題語句要求界定切片的總數，而不是列出它們。另一種制定方法可能是找到所有最長的有界切片，我猜[這是O（N）]。 –

編輯：解決的方法是錯誤的（切片都應該重疊）

此代碼對jsfiddle

/* values N, K and A[] are given */ 

var number_of_slices = 0, current_max_bound = 0, current_position = 0; 
var current_value = A[current_position]; 
var current_max_bound_value; 

while (current_max_bound < N) { 

    current_max_bound_value = A[current_max_bound]; 

    if (Math.abs(current_max_bound_value - current_value) < K) { 

    current_max_bound = current_max_bound + 1; 


    } else { 

    number_of_slices = number_of_slices + 1; 
    current_max_bound = current_max_bound + 1; 
    current_position = current_max_bound; 
    current_value = A[current_position]; 
    } 
} 

console.log('result: ' + number_of_slices);

來源

2014-01-24 00:41:35 r3x

即使對於給定示例A = {3,5,7,6,3} k = 2，您的解決方案似乎也不起作用;預期結果9 – Pandrei

好的。讓我看看。謝謝 – r3x

一個解決方案已經張貼在這裏：

https://codility.com/media/train/solution-count-bounded-slices.pdf

來源

2014-11-19 02:06:42

如何減少計算O（N）有界切片數的時間複雜度？

回答

相關問題