找到许多子数组的开始和结束的算法？

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）时间内运行。