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

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]。因为第二个子数组从第 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 步)创建两个 bool 值。如果当前存在“沉默”，则一个为真，如果最后看到的值为零，则另一个为真。这两个应该都是真的。如果我们不假设数组的第一个元素之前有无限个零，那么如果数组中的第一个数字为零，就会出现问题。

步骤 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) 时间内运行。