找到許多子數組的開始和結束的算法？

Question

所以我有這個問題在C：

給定一個只包含0和1的數組（例如：[1,1,0,0,0,0,1,0,1,0,1,1]）。 我需要找到一個「振鈴間隔」的開始和相同的「振鈴間隔」的完成（可能有許多這樣的環，我們必須將每個的開始和結束存儲在2的矩陣中列）

「沉默」是至少有兩個0彼此相鄰時。 （在給定的陣列中，子陣列[0,0,0,0]是無聲的

「環間隔」是當沒有發生沉默時（例如在給定的陣列中，子陣列[1,1]（前2個值））和子陣列[1,0,1,0,1,1]（數組的結束））。

所以我們必須存儲[0,1]矩陣的第一排。 然後[6,11]。由於第二子陣列啓動第六屆指數，並在11結束。

我似乎無法更好地描述它，它的語言不同，而且比這更復雜..我希望你nderstand！

例子： 陣列= [0,0,0,0,1,0,1,1,1,0,0,0,1,0,0] 矩陣將是：[4,8] [12,12]

陣列= [1,0,0,1,1] 矩陣將是：[0,0] [3,4]

謝謝！

Answer 1

我有一個簡單的算法，你可以很容易地轉化爲C與一些研究。你也可以將它翻譯成基本上任何其他語言：

步驟1）創建兩個布爾值。如果當前有一個「沉默」，一個將是真的，如果最後一個值是零，另一個將是真的。這兩個都應該是真的。如果我們不假定在數組的第一個元素之前有無限的零，那麼如果數組中的第一個數字爲零，就會出現問題。

步驟2）遍歷數組並檢查以下兩個條件之一：a）如果看到1，將沉默設置爲false，則將previousZero設置爲false。如果這個1打破沉默，那麼將這個值存儲爲下一個範圍的開始。 b）如果該值爲零並且沒有靜音，則將previousZero設置爲true。如果previousZero已經是真的，那麼你已經達到了一個沉默，所以把沉默設置爲true，並將你的開始位置和結束位置存儲在你的輸出數組中。在這種情況下，您的最終位置將是當前位置-2以說明您剛纔檢查的零點。

步驟3）一旦您已經遍歷整個陣列，則需要確保您沒有結束有效範圍。如果沉默是虛假的，你知道你結束了一個有效的範圍。通過使用存儲在循環中的開始值和數組的末尾作爲結束值，將此範圍存儲在輸出數組中。

該算法在線性時間內運行。下面是一些僞代碼，讓你開始使用C或者你選擇的任何東西來實現你的實現。

findRing(Array arr) 
    bool silence = true, previousZero = true; 
    int currentBegin = 0, currentEnd = 0; 
    for(int i = 0; i<arr.length; i++) { 
     if(arr[i] == 1) 
      if(silence == true) 
       currentBegin = i; 
      silence = false; 
      previousZero = false; 
     else if(arr[i] == 0 && silence == false) 
      if(previousZero) 
       silence = true; 
       currentEnd = 1-2; 
       addToOutput(currentBegin, currentEnd); 
      else 
       previousZero = true; 
    } 
    if(silence == false) 
     currentEnd = arr.length - 1; 
     addToOutput(currentBegin, currentEnd); 

我在C++中實現了這個僞代碼，並得到了您在示例中提供的相同輸出。正如你所提到的那樣，它應該很容易在C或Matlab中實現，並在O（n）時間內運行。