C++ solution: avoid linear deleting repeating nums


  • 1
    M
            bool search(vector<int>& nums, int target) {
                /* most posted solutions here use linear time deleting repeating numbers. 
                   this will result in o(n) time while log time is possible. the solution below avoided linear deleting, 
                   and shall prove time complexity somehow. */
                vector<int> lstack, rstack;
                int len=nums.size();
                lstack.push_back(0);
                rstack.push_back(len-1);
                
                while (!lstack.empty()) {
                    int l=lstack.back(), r=rstack.back();
                    lstack.pop_back();
                    rstack.pop_back();
                    
                    while (l<=r) {
                        int m=l+(r-l)/2;
                        if (nums[m]==target)
                            return true;
                            
                        if (nums[m] < nums[r] || nums[m] < nums[l]) {
                            if (nums[m]<target && target<=nums[r])
                                l=m+1;
                            else
                                r=m-1;
                        } else if (nums[m] > nums[r] || nums[m] > nums[l]) {
                            if (nums[l]<=target && target<nums[m])
                                r=m-1;
                            else
                                l=m+1;
                        } else {
                            /* nums[l]=nums[m]=nums[r], we search for left half, and save right half for later */
                            lstack.push_back(m+1);
                            rstack.push_back(r);
                            r=m-1;
                        }
                    }
                    
                }
                
                return false;
            }

Log in to reply
 

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