C 数组中最长的 1 序列

Question

我有一个像这样的数组：

0011011100011111001

我想找到这个数组中最长的 1 序列，记下起始点的长度和位置，这里长度为 5，起始点为 12。

有什么想法吗怎么办？

Answer 1

我同意这看起来像家庭作业，但我要做的方法是存储当前 1 的运行和最长运行的开始和长度。迭代数组。每当从 0 变为 1 时，更新当前起始位置并将长度设置为 1。当长度大于最长时，更新最长长度和起始点。就输入的长度而言，其运行时间复杂度为 O(n)。这不包括边缘情况，例如没有 1 的数组。

Answer 2

迭代数组，保留迄今为止找到的最大连续数的计数，以及当前连续数的单独计数。

let max_consec = 0
let curr_consec = 0
let i = 0
while i < array.size:
    if array[i] is 1:
        curr_consec++
    else:
        max_consec = Max(max_consec, curr_consec)
        curr_consec = 0
    i++

稍微思考一下，您应该能够自己弄清楚如何跟踪起始位置。

Answer 3

您可以将起始位置和长度最初设置为零，然后逐一遍历数组元素，使用简单的状态机跟踪 1 和 0 之间的转换。

状态表如下所示：

              +----------------------------------------+
              |               lastNum                  |
              +------------------+---------------------+
              |         0        |          1          |
+---------+---+------------------+---------------------+
|         | 0 | Just get next    | Check/update runLen |
|         |   |  character       |  against previous   |
| thisNum +---+------------------+---------------------+
|         | 1 | Store runPos  ,  | Increment runLen    |
|         |   |  set runLen to 0 |                     |
+---------+---+------------------+---------------------+

由于您只对 1 序列感兴趣，因此初始状态将 lastNum 设置为零以确保 1在开始时正确开始运行。我们还将初始的“迄今为止最大的运行”设置为大小和位置为零，以确保它被第一次真实运行覆盖。

此方法有一个特殊的边缘情况，因为我们必须检测列表中的最终数字是否为 1 - 如果是，则意味着不会有 1 -> 。 0 转换位于列表末尾，用于检查 1 数字的最终运行。

由于我们将在不检查最终运行的情况下退出循环，因此我们会进行最终检查，就像我们从 1 转换到 0 一样。

伪代码是这样的。首先，初始化所有变量：

# Store the current maximum run of '1' characters (none) and initial state.

var maxLen = 0, maxPos = 0, lastNum = 0

# runLen and runPos will be set in a 0->1 transition before we use them.

var rnLen, runPos

然后我们可以简单地迭代列表中的每个数字并按照上图检测转换：

# Iterate over entire list, one by one.

for curPos = 0 to len(list) - 1:
    # 0 -> 0: do nothing.

    # 0 -> 1: store position, set run length to 1.

    if lastNum == 0 and list[curPos] == 1:
        runPos = curPos
        runLen = 1
    endif

    # 1 -> 1: increment the current run length.

    if lastNum == 1 and list[curPos] == 1:
        runLen = runLen + 1
    endif

    # 1 -> 0: check current run against greatest to date.

    if lastNum == 1 and list[curPos] == 0:
        if runLen > maxLen:
            maxPos = runPos
            maxLen = runLen
        endif
    endif

    # Save current number into lastNum for next iteration.

    lastNum = list[curPos]
endfor

然后，最后，处理上述边缘情况：

# If we finished with a `1`, need to check final run.

if lastNum = 1:
    if runLen > maxLen:
        maxPos = runPos
        maxLen = runLen
    endif
endif