Find most of the O(n) submissions are actually O(n^2).Mine is truly O(nlgn) with binary search.


  • 0
    E

    Most of the O(n) (actually O(n^2)) submissions are from back to front. Mine is from front to the back.
    e.p.For {8,10,4,6,1,3,5}, we actually process a problem like this:
    We should test if the next number is in the 'segments':
    4 is not in segments{8-10}
    6 is the same, and expand the segments{4-6, 8-10}
    1 is not in segments{4-6, 8-10}
    3 is the same, and expand the segments{1-3, 4-6, 8-10}
    5 is in the segments{4-6}
    So return TRUE.
    And this algorithm can use binary search.

    typedef pair<int,int> p_type;
    class Solution {
    public:
        bool find132pattern(vector<int>& nums) {
            if(nums.size()<3)return 0;
            deque<p_type>ds;
            int m=nums[0];
            for(int i=1;i<nums.size();i++)if(b_s(ds,nums[i],m))return 1;
            return 0;
        }
        bool b_s(deque<p_type>&ds,int t,int&m){
            int st=0,en=ds.size()-1;
            int p=-1;
            while(st<=en){
                if(t<ds[st].first){p=st-1;break;}
                if(t>ds[en].first){p=en;break;}
                int mid=(st+en)/2;
                if(ds[mid].first==t){p=mid;break;}
                if(t>ds[mid].first)st=mid+1;
                else en=mid-1;
            }
            if(p==-1){
                if(t>m)ds.push_front(p_type(m,t));
                else m=t;
            }
            else{
                if(t>ds[p].first&&t<ds[p].second)return 1;
                int p2=t>ds[p].second?t:ds[p].second;
                ds.erase(ds.begin(),ds.begin()+p+1);
                ds.push_front(p_type(m,p2));
            }
            return 0;
        }
    };
    

Log in to reply
 

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