获取数组的所有连续相同数字块

Question

我这里有一个数组

int arr[] = { 2, 6, 6, 3, -1, -1, -1, 4, -1, -1, 5, 5, -1, 7 };
//                        ^^^^^^^^^^     ^^^^^^

我想编写一个代码来获取数组中连续 -1 的块数，但只获取包含多个 -1.

的块数

在此示例中，数组中有一个由三个连续的 -1 和两个连续的 -1 组成的序列，我想像这样获取两个序列的大小：

3 2

Answer 1

试试下面的代码：

int arr[] = { 2, 3, -1, -1, -1, 4, -1, -1};
int curr_cnt = 0;    
for(int i = 0; i < 8; i++){
    if(arr[i] == -1) curr_cnt++;
    else{
        if(curr_cnt != 0)   cout << curr_cnt << endl;
        curr_cnt = 0;
    }
}
if(curr_cnt != 0)   cout << curr_cnt << endl;

这里我们维护一个curr_cnt变量来存储连续-1的次数。如果我们得到 arr[i] 为 -1，我们简单地增加这个计数，否则将这个计数设置为 0，因为我们已经找到了一些其他元素。但是在将计数更新为零之前，如果计数大于 0，我们可以打印计数的值。因此，我们将获得所有连续 -1 的计数。

Answer 2

#include <iostream>

using namespace std;
int main(int argc, char** argv) {

int arr[] = { 2, 3, -1, -1, -1, 4, -1, -1 };
int save[4]; // at the worth case we have 4 contiguous ( 4 single -1 )
int counter_of_minus_one=0; // counter of -1 in every contiguous
int counter_of_contiguous=0; // counter of contiguous we have 
bool are_we_looking_for_new_contiguous=true; // this mean we are searching for new contiguous
int n=8;

for(int i=0;i<n;i++)
{
    if(are_we_looking_for_new_contiguous==true && arr[i]==-1)  //this means the -1 we found is our first -1 in our new contiguous
    {
        counter_of_minus_one++;   // +1 for our -1 counter
        counter_of_contiguous++; // +1 for our contiguous counter
        are_we_looking_for_new_contiguous=false; // so we set flag as false (that means whenever we seen a -1 it's the countinue of current contiguous)
    }
    else if(are_we_looking_for_new_contiguous==false && arr[i]==-1) // as we said what is flag==false so if we seen -1 it's the countinue of current contiguous
    {
        counter_of_minus_one++;
    }
    else if(are_we_looking_for_new_contiguous== false && arr[i]!=-1)//if flag==false but the arr[i] isn't -1 this mean we are out of the -1's contiguous then we close this contiguous and search for a new one
    {
        save[counter_of_contiguous-1]=counter_of_minus_one; // saving count of -1 for this countiguous
        counter_of_minus_one=0; // reset the -1 counter
        are_we_looking_for_new_contiguous=true; // looking for new contiguous for next i
    }
    else if(are_we_looking_for_new_contiguous==true && arr[i]!=-1)// flag==true means we are searching for new contiguous so we just go for next element in array
    {
        // doing nothing 
    }
    
    if(i==n-1 && are_we_looking_for_new_contiguous== false && arr[i]==-1) // if the last element be -1 we should add another if seprate of others to just save the last search
    {
        save[counter_of_contiguous-1]=counter_of_minus_one; // saving count of -1 for this countiguous
    }
}

for(int i=0;i<counter_of_contiguous;i++)
{
    cout<<save[i]<<endl; //printing result
}

return 0;}

Answer 3

你可能会：

template <typename IT, typename T>
std::vector<std::size_t> count_contiguous_block(IT begin, IT end, const T& value)
{
    std::vector<std::size_t> res;
    auto it = begin;
    do {
        it = std::find(it, end, value);
        auto endBlock = std::find_if(it, end, [](const auto& e){ return e != value; });
        if (it != endBlock) {
            res.push_back(std::distance(it, endBlock));
            it = endBlock;
        }
    } while (it != end)
    return res;
}

Demo

Answer 4

我想展示一个使用 C++ 语言元素的解决方案。

我在这里看到的一切（除了std::cout的用法）都是纯粹的C-code。很遗憾，因为 C++ 更强大并且有很多“of-the-shell”可用的算法。

因此，作为第一个注释。你不应该在 C++ 中使用 C-Style 数组。没有理由不使用 std::array 代替。或者，对于具有动态内存管理的用例，std::vector。使用 std::vector 几乎总是更好的解决方案。

无论如何。 C++ 也仍然可以使用 C-Style 数组。在下面的示例中，我大量使用了 C++ 功能并且仍然可以使用 C-Style 数组。由于这种编程风格，我可以稍后将 C-Style 数组与现代 C++ STL 容器交换，并且程序仍然运行.

但是让我们先看代码，稍后我会解释。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

// Test data
int arr[] = { 2, 3, -1, -1, -1, 4, -1, -1 };
unsigned int result[(sizeof(arr) / sizeof(arr[0]))/2];

// A predicate function that checks for 2 elements to be -1
bool twoMinusOnes(const int i, const int j) {
    return i == -1 && j == -1;
}

// Test program
int main() {

    // Here we count, how many contiguos blocks of -1 are available
    unsigned int blockCounter = 0;

    // Some iterator to the begin and end of a -1 block in a source data
    decltype(std::begin(arr)) beginOfBlock{};
    decltype(std::begin(arr)) endOfBlock{};

    // Find all blocks with contiguos -1 in a simple for loop
    for (   beginOfBlock = std::adjacent_find(std::begin(arr), std::end(arr), twoMinusOnes); // Initial value. Start searching from beginning
            beginOfBlock != std::end(arr);                                                   // Check end condition 
            beginOfBlock = std::adjacent_find(endOfBlock, std::end(arr), twoMinusOnes)) {    // find next block

        // Ok. std::adjacent_found a block with at lease 2 repeating -1 for us
        // Now, find the position, where this block ends
        endOfBlock = std::adjacent_find(beginOfBlock, std::end(arr), std::not_equal_to<int>());

        // Set iterator to past the end of the contiguous -1 block (if we are not at the end)
        if (endOfBlock != std::end(arr)) std::advance(endOfBlock, 1);

        // Store number of elements in this block
        result[blockCounter++] = std::distance(beginOfBlock, endOfBlock);
    }

    // Show result to user. Number of blocks and number of elements in each block
    for (unsigned int i{}; i < blockCounter; ++i)
        std::cout << "Block " << i + 1 << " has " << result[i] << " elements\n";

    return 0;
}

好的，我们在这里做什么？

首先，我们定义一个包含要检查的源数据的数组。其次，我们还定义了一个“结果”数组，具有固定的最大大小，等于第一个数组元素数的一半。这是因为不能有更多连续的 -1 块。

好的，然后我们定义一个所谓的谓词函数，它简单地检查两个给定元素是否都是-1。这就是我们在源数组中寻找的。然后可以在 C++ 标准算法中使用谓词函数。

在 main 中，我们初始化一个 blockCounter，它将显示找到的连续 -1 块的数量。

然后我们看到：

decltype(std::begin(arr)) beginOfBlock{};
decltype(std::begin(arr)) endOfBlock{};

这将定义一个迭代器，而不考虑使用的 C++ STL 容器。对于我们的 int[] 数组，它将是 int* （因此，我们也可以写成 int *beginOfBlock;.

这是一种非常灵活的方法，以后我们可以使用不同的容器。

接下来我们开始一个 for 循环，找到所有连续的 -1 块。

为此，我们使用专门的函数来查找具有特定属性的相邻元素：std::adjacent:find。请参阅 here 以获取参考说明。标准是找到相等的元素。但是我们使用谓词函数找到 2 个连续的 -1。

所以，for-loop的init语句，寻找这样一个块，从容器的开头开始。 for 的“条件”检查是否可以找到块。

并且“iteration_expression”在第一个块被评估后寻找下一个块。

这是一个正常的 for 循环，相当简单。

在循环body中，我们只有3条语句：

搜索当前找到的-1块的末尾
因为该函数将 return 一对中的第一个元素，它将指向找到的块的最后一个 -1。我们将增加位置以指向找到的 -1 块之后的下一个元素（但前提是我们还没有到达数组的末尾）
我们将结果元素数存储在一个块中

就是这样。非常简单紧凑的代码。

最后我们在控制台上显示收集的结果。

基本上就是这样。由于重用了标准 C++ 库中的现有函数，因此只需要几条语句。

为了向您展示这种函数的通用性，您可以 include header vector 然后简单地通过以下方式替换您的 C-Style 数组：

// Test data
std::vector arr{ 2, 3, -1, -1, -1, 4, -1, -1 };
std::vector<size_t> result(arr.size()/2);

程序将像以前一样运行。

如果你想学习 C++，我强烈建议你开始使用 C++ 语言元素

如有问题，请提问。

Answer 5

使用 range-v3 库，您可以以一种非常易读的方式实现它，一旦您习惯了这种事情。先写一些方便的命名空间别名：

namespace rs = ranges;
namespace rv = ranges::views;

现在您需要实现的主要逻辑是确定相同数字的连续块是否有效。

auto is_valid_block = [](auto block)   // block of same numbers 
{
  return *rs::begin(block) == -1       // containing -1s
         and rs::size(block) > 1;      // and at least 2 of them
};

现在您可以将范围分组为相同编号的块，并根据您的约束过滤这些块。

for (auto block : arr                           // [ 2 6 6 3 -1 -1 -1 4 -1 -1 5 5 -1 7 ]     
                | rv::group_by(std::equal_to{}) // [ [2] [6 6] [3] [-1 -1 -1] [4] [-1 -1] [5 5] [-1] [7] ]     
                | rv::filter(is_valid_block))   // [ [-1 -1 -1] [-1 -1] ]     
    std::cout << rs::size(block) << " ";        // 3 2

这里是 demo。

获取数组的所有连续相同数字块

Get all blocks of contiguous same numbers for an array

c++

arrays

contiguous