My C++ solution with minimum elements moving in the array


  • 0
    S
    int removeElement(int A[], int n, int elem) {
    
        //loop invariant: A[i,j] has the elements we haven't checked
        //A[0,i-1] has the elements that are not elem
        //A[j+1,n-1] has the elments that are removed
        //Before the loop the above two arrays are both empty
        //At end of the loop new array length is either i or j+1;
        int i=0,j=n-1; 
    
        while(i<=j){
            if(A[i] == elem){
                while(j>i && A[j]==elem)
                    j--;
                if(i==j)
                    return i;
                A[i]=A[j];
                j--;
                i++;
            }
            else
                i++;
        }
        
        return j+1;
    }

  • 0
    Z
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0

    This problem is similar to part of quick sort.

    class Solution {
        public:
            int removeElement(int A[], int n, int elem) {
                int *p = A, *q = A + n - 1;
                for (;;)
                {
                    while (p <= q && *p != elem)
                    {
                        ++p;
                    } 
        
                    while (q > p && *q == elem)
                    {
                        --q;
                    }
        
                    if (p >= q )
                    {
                        return (p - A);
                    }
        
                    std::swap(*p, *q);
                }
            }
        };

Log in to reply
 

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