pseudocode - 伪代码查找数组中最长的运行

Question

我知道 A 运行是一系列相邻的重复值，你将如何编写伪代码来计算数组中最长运行的长度，例如

5 将是这个整数数组中最长的一次。

1 2 4 4 3 1 2 4 3 5 5 5 5 3 6 5 5 6 3 1

任何想法都会有所帮助。

Answer 1

def longest_run(array):
  result = None
  prev = None
  size = 0
  max_size = 0
  for element in array:
    if (element == prev):
      size += 1
      if size > max_size:
        result = element
        max_size = size
    else:
      size = 0
    prev = element
  return result

编辑

哇。哇！这个伪代码实际上是有效的：

>>> longest_run([1,2,4,4,3,1,2,4,3,5,5,5,5,3,6,5,5,6,3,1])
5

Answer 2

max_run_length = 0;
current_run_length = 0;
loop through the array storing the current index value, and the previous index's value 
  if the value is the same as the previous one, current_run_length++;
  otherwise {
    if current_run_length > max_run_length : max_run_length = current_run_length
    current_run_length = 1;
  }

Answer 3

int main()
{
    int a[20] = {1, 2, 4, 4, 3, 1, 2, 4, 3, 5, 5, 5, 5, 3, 6, 5, 5, 6, 3, 1};
    int c=0;
    for (int i=0;i<19;i++)
    {
        if (a[i] == a[i+1])
        {
            if (i != (i+1))
            {
                c++;
            }
        }
    }
    cout << c-1;
    return 0;
}

Answer 4

这是 Python 中的一种不同的函数方法（Python 看起来像伪代码）。此代码仅适用于 Python 3.3+。否则，您必须将“return”替换为“raise StopIteration”。

我正在使用生成器来生成一个包含元素数量和元素本身的元组。它更具普遍性。您也可以将其用于无限序列。如果要从序列中得到最长的重复元素，它必须是一个有限序列。

def group_same(iterable):
    iterator = iter(iterable)
    last = next(iterator)
    counter = 1
    while True:
        try:
            element = next(iterator)
            if element is last:
                counter += 1
                continue
            else:
                yield (counter, last)
                counter = 1
                last = element
        except StopIteration:
            yield (counter, last)
            return

如果你有这样的列表：

li = [0, 0, 2, 1, 1, 1, 1, 1, 5, 5, 6, 7, 7, 7, 12, 'Text', 'Text', 'Text2']

然后你可以创建一个新的列表：

list(group_same(li))

然后你会得到一个新的列表：

[(2, 0),
 (1, 2),
 (5, 1),
 (2, 5),
 (1, 6),
 (3, 7),
 (1, 12),
 (2, 'Text'),
 (1, 'Text2')]

要获得最长的重复元素，可以使用 max 函数。

gen = group_same(li) # Generator, does nothing until iterating over it
grouped_elements = list(gen) # iterate over the generator until it's exhausted
longest = max(grouped_elements, key=lambda x: x[0])

或作为一个班轮：

max(list(group_same(li)), key=lambda x: x[0])

函数 max 为我们提供了列表中最大的元素。在这种情况下，列表有多个元素。参数键仅用于获取元组的第一个元素作为最大值，但您仍然会取回元组。

In : max(list(group_same(li)), key=lambda x: x[0])
Out: (5, 1)

元素 1 重复出现 5 次。