How to find the biggest sequence of some number pa

问题:

I have vector of numbers std::vector numbers; How to find the biggest sequence of some number passed like parameter ? For example if I have like 0, 1, 1 , 3 , 2 , 0 , 0, 0, 6 , 0 , 0 and I am looking for 0 number I need to get start index 5 in this case. Is there already some functions or combinations to achieve in stl or boost for this problem ? ( I cannot use C++11 )

回答1:

I do not think there is a standard function that does this for you, but you can program a relatively straightforward algorithm for it:

int max_len = -1;
int best_index = -1;
int count = 0;
vector<int> data;
int value;
// Set the data and value here...
for (int i = 0 ; i != data.size() ; i++) {
    if (data[i] == value) {
        count++;
    } else {
        if (count > max_len) {
            best_index = i - count;
            max_len = count;
        }
        count = 0;
    }
}
if (count > max_len) {
    best_index = i - count;
    max_len = count;
}

回答2:

I don't think you'll do better than a brute force counting of the runs in the vector as you iterate over each member.

回答3:

Is it really necessary to use a lib function for this?

A simple approach -- and i don't see anything more efficient at hand --, would be to pick the first number and count it as long as it appears in sequence.

If another number appears, you count it until another one comes up, and then compare the frequency of the last one with the one just counted, maintaining always the one with the greatest frequency, and doing this until you reach the end of the list -- or until you can affirm that, given the size of the list, and the position you are in the list, no number could be more frequent, in a sequence, than the one you already have as most frequent.