Evolve from brute force to optimal, a review of all solutions


  • 1

    This is similar to Count of Smaller Numbers After Self. Solutions are very similar.

    1. O(n^2) brute force
        int reversePairs(vector<int>& nums) {
            int n = nums.size(), res=0;
            for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(nums[i]/2.0>nums[j]) res++;
            return res;    
        }
    
    1. O(n^2) Brute force with binary search.
        int reversePairs(vector<int>& nums) {
            int n = nums.size(), res=0;
            if(!n) return 0;
            vector<int> vstd(1,nums.back());
            for(int i=n-2;i>=0;i--) {
                res += lower_bound(vstd.begin(),vstd.end(),(double)nums[i]/2) - vstd.begin();
                vstd.insert(lower_bound(vstd.begin(),vstd.end(),nums[i]), nums[i]);
            }
            return res;    
        }
    
    1. Average O(nlogn), worst O(n^2) binary search tree.
        class Node {
            public:
            Node (int val):val_(val),left_(NULL),right_(NULL),lt_(0){}
            Node *left_,*right_;
            int lt_,val_;
        };
        void insert(int val, Node *rt) {
            Node **r = &rt; 
            while(*r)
                if(val<(*r)->val_) {
                    (*r)->lt_++;
                    r=&(*r)->left_;
                } else r=&(*r)->right_;
            *r= new Node(val);
        }
        int countSmaller(double val, Node* r) {
            int ct = 0;
            while(r)
                if(val<r->val_) r = r->left_;
                else {
                    ct += r->lt_+(val>r->val_);
                    r=r->right_;
                }
            return ct;  
        }
        void dlt(Node *r) {
            if(!r) return;
            dlt(r->left_);
            dlt(r->right_);
            delete r;
        }
        int reversePairs(vector<int>& nums) {
            if(nums.empty()) return 0;
            int n=nums.size(), res=0;
            Node *r=new Node(nums.back());
            for(int i=n-2;i>=0;i--) {
                res+=countSmaller(nums[i]/2.0,r);
                insert(nums[i],r);
            }
            dlt(r);
            return res;
        }
    
    1. O(nlogn) binary index tree.
        int reversePairs(vector<int>& nums) {
            vector<int> sorted=nums;
            sort(sorted.begin(),sorted.end());
            int n = nums.size(), res = 0;
            vector<int> bit(n+1);
            unordered_map<int,int> index;
            for(int i=0;i<n;i++) index[sorted[i]]=i+1;
            for(int i=n-1;i>=0;i--) {
                res+=getSum(lower_bound(sorted.begin(),sorted.end(),nums[i]/2.0)-sorted.begin(),bit);
                update(index[nums[i]],bit);
            }
            return res;
        }
        int getSum(int i, vector<int>& bit) {
            int sum = 0;
            while(i) {
                sum+=bit[i];
                i&=i-1;
            }
            return sum;
        }
        void update(int i, vector<int>& bit) {
            while(i<bit.size()) {
                bit[i]++;
                i+=i&-i;
            }    
        }
    
    1. O(nlogn) merge sort.
        int reversePairs(vector<int>& nums) {
            return mergeSort(0,nums.size()-1,nums);
        }
       int mergeSort(int l, int r, vector<int>& nums) {
            if(l>=r) return 0;
            int mid=(r-l)/2+l, count = mergeSort(l,mid,nums) + mergeSort(mid+1,r,nums);
            for(int i=l,j=mid+1;i<=mid;i++) {
                while(j<=r && nums[i]/2.0>nums[j]) j++;
                count+=j-mid-1;
            }
            int i=l,j=mid+1,k=0;
            vector<int> merge(r-l+1);
            while(i<=mid || j<=r)
                if(j>r || (i<=mid && nums[i]<=nums[j])) merge[k++]=nums[i++];
                else merge[k++]=nums[j++];
            copy(merge.begin(),merge.end(),nums.begin()+l);
            return count;
        }
    

Log in to reply
 

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