c++ - 如何在数组中找到第一组最长的连续重复项的起始索引

Question

给定

int array[5] = { 0, 0, 1, 1, 1 }

其中数组可以是 0 和 1 的任何可能排列，并且总是至少有一个 1，我想找到（第一个）最长的连续 1 集的起始索引。示例：

int array[5] = { 0, 1, 1, 0, 0 } -> index = 1
int array[5] = { 1, 0, 0, 0, 0 } -> index = 0
int array[5] = { 1, 0, 1, 0, 1 } -> index = 0
int array[5] = { 1, 0, 0, 1, 1 } -> index = 3

如果它更容易，它也可以是一个 char 数组。如果我不清楚，请告诉我。

标签： c++

Answer 1

如果您不关心性能，那么这个简单的实现应该适合您。

int index = -1, candidate_index = -1;
size_t array_size = 5, max_size = 0; 
for (size_t i = 0; i < array_size; ++i) {
    if (array[i] == 0) {
        if (candidate_index >= 0) {
             size_t candidate_size = i - candidate_index + 1;
             if (candidate_size > max_size) {
                  max_size = candidate_size;
                  index = candidate_index;
             }
        }
        candidate_index = -1;
        continue;
    }
    // array[i] == 1 there
    if (candidate_index < 0) {
        candidate_index = i; 
    }
} 
// handling if the largest strip is at the end of the array
if (candidate_index >= 0) {
     size_t candidate_size = array_size - candidate_index;
     if (candidate_size > max_size) {
          index = candidate_index;
     }
}