gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:56:47 28 4
gpt4 key购买 nike

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

谢谢!

最佳答案

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

关于c - 找到许多子数组的开始和结束的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44186280/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com