查找多个子数组的开始和结束的算法？
所以我在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]。因为第二个子数组从第6个索引开始，到第11个索引结束。
我似乎无法更好地描述它，它用的是一种不同的语言，而且比这个要复杂得多。我希望你能理解！
例子:数组= [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]
谢谢!
回答 1
Stack Overflow用户
发布于 2017-05-25 18:18:02
我有一个简单的算法，您可以很容易地通过一些研究将其转换成C语言。你也可以把它翻译成任何其他语言：
步骤1)创建两个布尔值。如果当前存在“沉默”，则其中一个为真；如果最后看到的值为零，则另一个为真。这两件事都应该是真的。如果我们不假设数组的第一个元素之前有无穷零，那么如果数组中的第一个数字是零，就会出现问题。
步骤2)循环遍历数组，并根据以下两个条件之一进行检查: a)如果您看到一个1，将静默设置为false，将previousZero设置为false。如果这1打破沉默，存储此值，因为它是您下一个范围的开始。b)如果值为零，且不存在沉默，则将previousZero设置为true。如果previousZero已为真，则已达到静默状态，因此请将静默设置为真，并将开始位置和结束位置存储在输出数组中。在这种情况下，您的最终位置将是当前位置-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)时间内运行。
https://stackoverflow.com/questions/44186280
复制相似问题
腾讯云开发者
