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

Algorithm that finds the start and the finish of many sub-arrays?

所以我在 C:

中有这个问题

给定一个仅包含 0 和 1 的数组(示例:[1,1,0,0,0,0,1,0,1,0,1,1])。 我需要找到一个 "ring interval" 的开始和相同的 "ring interval" 的结束(可能有很多这样的环,我们必须将每个环的开始和结束存储在一个矩阵中2 列)

"Silence" 是指至少有两个 0 相邻。 (在给定的数组中,子数组[0,0,0,0]是无声的。

"Ring interval" 是 Silence 没有发生的时候。 (给定数组中的示例,子数组 [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]

谢谢!

我有一个简单的算法,你可以很容易地通过一些研究将其转换为 C。您也可以将其翻译成基本上任何其他语言:

步骤 1) 创建两个布尔值。如果当前存在 "silence",则一个为真,如果最后看到的值为零,则另一个为真。这两个应该都是真的。如果我们不假设数组的第一个元素之前有无限个零,那么如果数组的第一个数为零,就会出现问题。

步骤 2) 遍历数组并检查 2 个条件之一:a) 如果看到 1,将 silence 设置为 false,将 previousZero 设置为 false。如果这个 1 打破沉默,存储这个值,因为它是你下一个范围的开始。 b) 如果该值为零并且没有静音,则将 previousZero 设置为 true。如果 previousZero 已经为真,则表示您已进入静默状态,因此将静默设置为真并将开始位置和结束位置存储在输出数组中。在这种情况下,您的最终位置将是当前位置 -2,以说明您刚刚检查的零

步骤 3) 循环遍历整个数组后,您需要确保没有在有效范围内结束。如果 silence 为假,你知道你在一个有效范围内结束。通过使用存储在循环中的开始值和数组的结尾作为结束值,将此范围存储在输出数组中。

该算法以线性时间运行。下面是一些伪代码,可帮助您开始使用 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) 时间内运行。