Suppose I have a list of number: [0 0 1 1 1 0 1 1 0 1 0 0 0 1 1], which is composed of either 0 or 1,and my problem is how to find the beginning and ending positions of the number 1 in the list. Take the above list of number as an example, and the positions of a list of 1 are:
[2 4]
[6 7]
[9 9]
[13 14]
Using C++, the following method is implemented:
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;
}
Are there more efficient solutions (either in time or in space) to this problem? Thanks.
The solution I will suggest is not more efficient but looks better.:)
Try the following
#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;
}
The output is
[2 4]
[6 7]
[9 9]
[13 14]
If the array consists only from 0 and 1 then you may substitute this statement
auto last = std::find_if( first, std::end( charArray ),
std::bind2nd( std::not_equal_to<int>(), 1 ) );
for this one
auto last = std::find( first, std::end( charArray ), 0 );
In this case the loop will look like
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;
}
To write a more efficient code you have to reserve memory for the vector.
For example
#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;
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다