jeudi 31 janvier 2019

A question of efficiency : A boolean function to return a change in a vector and true/false

I am trying to create a function which takes 2 numbers as a range of values of a vector. It pushes all the numbers to the left and adds two adjacent numbers if they are equal. For example:

v (before):

[0 0 0 5 1 2 0 2 2 0 0 0 2 0 0 2 6 0 0 5 0 6 4]

bi: 1

ei: 4


v (after):

[0 5 0 0 1 2 0 2 2 0 0 0 2 0 0 2 6 0 0 5 0 6 4]

return: true

The function:

bool left_push(std::vector<int>& v, int bi, int ei){

    std::vector<int> tmp;
    bool check = false ;

    for(int i = bi+2 ; i <= ei ; i++){

        if(v[i]==v[i-1]){
            v[i-1] = v[i]+v[i];
            v[i] = 0;

            check = true;
        }

        if(v[i-1]==0){
            v[i-1] == v[i];
            v[i] = 0;

            check = true ;
        }

    return check;
}

The issue with this is that after it goes through this code one whole time, It would not have yet reached a point where it fully pushes all the numbers to the left and adds them to the left. For example say we just added two numbers e.g 2 2 this means we now have 4 0 and so not all the zeros would be pushed to the left.

This mean I need to perform this whole thing multiple times by putting it all into a for loop. The problem with this is that this would lead to inefficiencies as you could be going through the loop even after all possible movements have happened.

I have tried doing it in other methods. For example, remove all the zeros and then add them but even then you still get the same problems.

How exactly could I overcome this issue? I would appreciate any ideas/pointers.

Aucun commentaire:

Enregistrer un commentaire