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

Question

所以我在 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]

谢谢！

Answer 1

我有一个简单的算法，你可以很容易地通过一些研究将其转换为 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) 时间内运行。

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

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

c

arrays

algorithm

sequence

sub-array