No extra memory


  • 0
    Y

    Most solutions posted use extra memory. In order to avoid this, we make use of the given vector/array. The trick is to remove first three entries of the given array after checking the identity of v[0]. It remains to check whether the element v[0] occurs three times or not; if its occurrence is not 3, return v[0] as we already found the required element. If not, clear the first three elements and proceed using the familiar bit operation.

    This solution also requires two additional indexing variables i and j. I think some kind of loop is needed.

    class Solution {
    public:
        int singleNumber(vector<int>& v) {
            for (int j=1; j<=3; j++)
                for (int i=j; i<v.size(); i++)
                    if(v[0]==v[i]) swap(v[i],v[j]);
    
            if(v[0]!=v[1]||v[0]!=v[2]) return v[0];
            if(v[0]==v[3]) return v[0];
    
            v[0]=v[1]=v[2]=0;
            for (int i=3; i<v.size(); i++)
                v[0]^=v[i],
                v[1]|=(v[0]^v[i])&v[i],
                v[2]=~(v[0]&v[1]),
                v[0]&=v[2],
                v[1]&=v[2];
            return v[0];
        }
    };

  • 0
    A
    This post is deleted!

Log in to reply
 

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