What about my O(n) solution


  • 0
    J

    Here is the code in C++.

    class Solution {
    public:
        int removeElement(int A[], int n, int elem) {
            if (n == 0) return 0;
    	 
        	 int newLength = n;
        	 for (int index = 0; index != newLength; ++index)
        	 {
        		 if (A[index] == elem)
        		 {
        			 // Use the last element to cover the current element
        			 // And decrease the newLength by 1
        			 A[index] = A[newLength-1];
        			 --newLength;
        			 // Decrease the index so that the new current element
        			 // can be checked in next loop
        			 --index;
        		 }
        	 }
        	 return newLength;
        }
    };
    

    Any better ?


  • 0
    G

    Did you verify that this works? What if the last element you use to cover the current element IS the element? You don't seem to check for that.


  • 0
    J

    If the last element you use to cover the current element IS the element, it means that the current element is the last one. And "--newLength;" will make it work.


  • 1

    Don't really need to do these + and - on index

         int backP = n - 1;
         int index = 0;
         
         while(index <= backP)
         {
             if (A[index] == elem)
             {
                 A[index] = A[backP];
                 --backP;
             } else
             {
                 ++index;
             }
         }
         return index;
    

    Use while instead, same time cost, easier to read


  • 0
    K

    check [1,2,3,4,5,6,7,8,9,1], 1
    the origin array's last element is already the same as the supplied element


  • 0
    J

    Test case [1,2,3,4,5,6,7,8,9,1], 1 passed. You can debug the code in the IDE by yourself, I think.


Log in to reply
 

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