C++ merge sort solution, very short


  • 16
    5
    class Solution {
    public:
        int mergeSort(vector<long>& sum, int lower, int upper, int low, int high)
        {
            if(high-low <= 1) return 0;
            int mid = (low+high)/2, m = mid, n = mid, count =0;
            count =mergeSort(sum,lower,upper,low,mid) +mergeSort(sum,lower,upper,mid,high);
            for(int i =low; i< mid; i++)
            {
                while(m < high && sum[m] - sum[i] < lower) m++;
                while(n < high && sum[n] - sum[i] <= upper) n++;
                count += n - m;
            }
            inplace_merge(sum.begin()+low, sum.begin()+mid, sum.begin()+high);
            return count;
        }
    
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int len = nums.size();
            vector<long> sum(len + 1, 0);
            for(int i =0; i< len; i++) sum[i+1] = sum[i]+nums[i];
            return mergeSort(sum, lower, upper, 0, len+1);
        }
    };

  • 0
    X

    very nice solution !
    very nice solution !
    very nice solution !
    .


  • 0
    W

    inplace_merge???


  • 0
    Z

    Instead of
    int mid = (low+high)/2

    use

     int mid = low + (high-low)/2

  • 0
    D

    Is each mergeSort taking O(n^2)?

    for(int i =low; i< mid; i++)
        {
            while(m < high && sum[m] - sum[i] < lower) m++;
            while(n < high && sum[n] - sum[i] <= upper) n++;
            count += n - m;
        }
    

    Is this part taking O(n^2)?


  • 0
    5

    no, only O(n), m and n at most plus mid times


  • 0
    D

    i from low to mid; each time m and n can go from mid to high; so O(n/2)*O(n/2)=O(n^2). Am I wrong?


  • 0
    5

    m and n will keep increase rather than start from beginning each time, that means though for loop will run mid times, but while loop will at most run mid times too.


  • 0

    @508618087qq.com Quite clean one! Thanks, voting you up!


  • 0
    Q

    why can you do merge sort on the sum vector? That will change the order of the elements, why can you still use sum[m] -sum[i] as a criteria to increase m? Thanks.


  • 0

    @quesder You see here is the thing:

    • merge sort here is just to split the whole problem into two separate parts so there is a

    count =mergeSort(sum,lower,upper,low,mid) +mergeSort(sum,lower,upper,mid,high);

    but the sums that belong to the specified lower and higher can start from the left half to the right half (you must already be very clear about the prefix-sum, right? then this is not tricky for you)

    • after the merge sort the left and right parts are sorted, so for each left sum a, what we should do is to search for range that the prefix-sums in the right b can meet the condition lower <= b-a <= higher and then that range is the possible choice we have in the right part for that single index.

  • 0
    Q

    @LHearen
    Thanks. Another question, though may be silly. Why do we return 0 if high - low <= 1?
    If it is 1, shouldn't we try whether sum[high]-sun[end] is in range or not?


  • 0

    @quesder
    mergeSort(sum, lower, upper, 0, len+1);

    This statement, do you notice it? the last iterator is excluded so once high-low<=1 then there is only at most one element in the range.


  • 0

    @508618087qq.com
    Brilliant!


  • 0
    T

    Here is java version of your method:

    class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            if(nums==null || nums.length<1){
                return 0;
            }
            long[] sums = new long[nums.length];
            long sum = 0;
            for(int i=0;i<nums.length;i++){
                sum+=nums[i];
                sums[i] = sum;
            }
            int higher = upper;
            return merger(sums,0,sums.length-1,lower,higher);
        }
        
        public int merger(long[] sums,int start,int end,int lower,int higher){
            if(start>end){
                return 0;
            }else if(start==end){
                if(sums[start]>=lower&&sums[end]<=higher){
                    return 1;
                }
                return 0;
            }
            
            int mid = (start+end)>>>1;
            int count=merger(sums,start,mid,lower,higher)+merger(sums,mid+1,end,lower,higher);
            
            int lowerIndex = mid+1;
            int higherIndex = mid+1;
            for(int i=start;i<=mid;i++){
                while(lowerIndex<=end&&sums[lowerIndex]-sums[i]<lower){
                    lowerIndex++;
                }
                while(higherIndex<=end&&sums[higherIndex]-sums[i]<=higher){
                    higherIndex++;
                }
                count+=(higherIndex-lowerIndex);
            }
            mergerHelper(sums,start,mid,end);
            return count;
        }
        
        public void mergerHelper(long[] sums,int start,int mid,int end){
            int i = start;
            int j = mid+1;
            long[] copy = new long[end-start+1];
            int p=0;
            while(i<=mid&&j<=end){
                if(sums[i]<sums[j]){
                    copy[p++]=sums[i++];
                }else{
                    copy[p++] = sums[j++];
                }
            }
            
            while(i<=mid){
                copy[p++]=sums[i++];
            }
            while(j<=end){
                copy[p++] = sums[j++];
            }
            
            System.arraycopy(copy,0,sums,start,end-start+1);
        }
    }
    

  • 0
    T

    This one should be best solution!!!


  • 0
    W

    I have the same question.
    When when high - low == 1, for example, we have -2, whose index is 3
    and -2 is in the range of [lower,upper], if you return 0, you can't get [3,3]. Instead, we should judge whether it's in [lower, upper], and return 1 or 0.

    Am I correct ? Please tell me if I am wrong.


Log in to reply
 

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