C++ solution (4ms)


  • 1
    D

    Explanation:

    Let's assume for the sake of this explantation that 1 represents the unwanted element and x is a don't care which represent any other value different from that element.

    There are two steps in this program:

    I. I move all instances of the unwanted element to the far right of the array. So if the array looks like 1xx1xx111x
    it will end up being xxxxx11111. To do that, I always look for the next instance of 1 then move that value until its right neighbour is another 1 and so on, bringing together all the 1's. Note that I'll only move a 1 if its right neighbour is a different number from itself (an x). So after the first iteration, my initial array will look like xx11xx111x. The next iterations will yield:

    .

    xx1xx1111x
    xxxx11111x
    xxxx1111x1
        ....
        ....
    xxxx11x111
    xxxx1x1111
    xxxxx11111 (done)
    

    II. I now traverse the new array until i meet a 1. The index at which I met that 1 is also a counter of the array's length so I return that number.

    III. (Optional) Here I physically remove the unwanted values from the array. I believe this is what the exercise wanted us to do as it tells us to remove all instances of those elements but I don't think this step gets checked in the test cases as the solution still gets accepted without it.

    Code:

    int removeElement(vector<int>& nums, int val) {
    
        const unsigned int N = nums.size();
        bool done = false; //Checks if the array has been split in two sides
    
        if(N == 0) return 0;
    
        //1. Push all instances of unwanted value to the far right
        while(!done){
    
            // Assume that array has been split in two sides
            done = true;
    
            for(int i = 0; i < N-1;  i++){
    
                
                // find next instance of val
                if(nums[i] == val){
                    
                    int j = i;
                    // push it to the right as far as possible
                    while((nums[j] == val) && (nums[j+1] != val) && j < (N-1)){
                         done = false; 
                         std::swap(nums[j], nums[j+1]);
                         j++;
                    }
                }
            }
        }
    
        //2. Get index of first instance of unwanted value
        int i;
        for(i=0; i < N; i++)
            if(nums[i] == val) break;
    
    
        //3. (Optional) Remove values
        nums.erase(nums.begin() + i,nums.begin() + N);
    
        return i;
    
    }

  • 0
    O

    Good,i really appreciate it!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.