如何找到一个号码列表一定数量的列表的位置

Question

假设我有号码的清单：[0 0 1 1 1 0 1 1 0 1 0 0 0 1 1]，它是由0或1，和我的问题是如何找到的开始和结束位置列表中的编号为1。取数的上述列表作为一个例子，和1列表的位置是：

[2 4] 
[6 7] 
[9 9] 
[13 14] 

用C++，下面的方法被实现：

int main() 
{ 

    unsigned char charArray[15]={0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1}; 

    std::vector<std::pair<int,int> > posArray; 

    int begPos=-1; 
    int endPos=-1; 
    for(int i=0; i<15; i++) 
    { 
     if(charArray[i] ==1) 
     { 
      if(begPos!=-1) 
      { 
       endPos++; 
      } 
      else 
      { 
       begPos=i; 
       endPos=i; 
      } 
     } 
     else 
     { 
      if(begPos != -1) 
      { 
       posArray.push_back(std::make_pair<int,int>(begPos,endPos)); 
       begPos=-1; 
      } 

     } 

    } 
    if(charArray[14] == 1) 
    { 
     posArray.push_back(std::make_pair<int,int>(begPos,endPos)); 
    } 

    for(int i=0; i<posArray.size(); i++) 
    { 
     std::cout<<"("<<posArray[i].first<<" , "<<posArray[i].second<<")"<<std::endl; 
    } 
    return 0; 
} 

是否有更有效的解决方案（或在时间上还是在空间上）这个问题？谢谢。

Answer 1

的解决方案，我将建议是不是更有效，但看起来更好。:)

请尝试以下

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

int main() 
{ 
    unsigned char charArray[] = 
    { 
     0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1 
    }; 
    std::vector<std::pair<int,int> > posArray; 

    auto first = std::begin(charArray); 

    while ((first = std::find(first, std::end(charArray), 1)) != std::end(charArray)) 
    { 
     auto last = std::find_if(first, std::end(charArray), 
            std::bind2nd(std::not_equal_to<int>(), 1)); 

     posArray.push_back({ std::distance(charArray, first), 
           std::distance(charArray, last) - 1 }); 
     first = last;        
    } 

    for (auto &p : posArray) std::cout << '[' << p.first 
             << ' ' << p.second 
             << ']' << std::endl; 

    return 0; 
} 

输出是

[2 4] 
[6 7] 
[9 9] 
[13 14] 

如果数组从0只包括1，那么您可以替代这种说法

auto last = std::find_if(first, std::end(charArray), 
           std::bind2nd(std::not_equal_to<int>(), 1)); 

这一个

auto last = std::find(first, std::end(charArray), 0); 

在这种情况下，循环会像

while ((first = std::find(first, std::end(charArray), 1)) != std::end(charArray)) 
{ 
    auto last = std::find(first, std::end(charArray), 0); 

    posArray.push_back({ std::distance(charArray, first), 
          std::distance(charArray, last) - 1 }); 
    first = last;        
} 

要编写必须保留内存为载体更高效的代码。

例如

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <algorithm> 
#include <numeric> 
#include <utility> 
#include <functional> 

int main() 
{ 
    unsigned char charArray[] = 
    { 
     0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1 
    }; 
    std::vector<std::pair<int,int> > posArray; 

    size_t n = std::inner_product(std::next(std::begin(charArray)), 
            std::end(charArray), 
            std::begin(charArray), 
            0ul, 
            std::plus<size_t>(), 
            std::greater<char>()); 

    n += charArray[0] == 1; 

    posArray.reserve(n); 

    auto first = std::begin(charArray); 

    while ((first = std::find(first, std::end(charArray), 1)) != std::end(charArray)) 
    { 
     auto last = std::find(first, std::end(charArray), 0); 

     posArray.push_back({ std::distance(charArray, first), 
           std::distance(charArray, last) - 1 }); 
     first = last;        
    } 

    for (auto &p : posArray) std::cout << '[' << p.first 
             << ' ' << p.second 
             << ']' << std::endl; 

    return 0; 
} 

Answer 2

无法抗拒。这里是我的两个penneth：

int main() 
{ 
    unsigned char charArray[] = {0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1}; 

    std::vector<std::pair<int,int> > posArray; 

    size_t found[2]; 
    unsigned char seek = 0; 

    for(size_t i = 0; i < sizeof(charArray); ++i) 
    { 
     if(seek == charArray[i]) 
      continue; 

     found[seek] = i - seek; 

     if(!(seek ^= 1)) 
      posArray.push_back(std::make_pair(found[0], found[1])); 
    } 

    if(seek) 
     posArray.push_back(std::make_pair(found[0], sizeof(charArray) - 1)); 

    for(int i = 0; i < posArray.size(); i++) 
     std::cout << "[" << posArray[i].first 
      << " , " << posArray[i].second << "]" << '\n'; 
} 

输出

[2 , 4] 
[6 , 7] 
[9 , 9] 
[13 , 14]