C++ O(nlogn)-Time O(n)-Space MergeSort Solution with Detail Explanation


  • 71

    MergeSort-based solution is a standard way to solve problems related to inverse numbers.

    Here is an example to illustrate the general idea of MergeSort-based algorithm:

    Now we want to consider an array

                6 4 1 8 7 5 2 9
    

    First thing first, split the array into to subarrays:

                6 4 1 8
                7 5 2 9
    

    and then calculate the inverse numbers within the group:

                      1 4(1) 6(1,4) 8
                      2 5(2) 7(2,5) 9
    

    where the numbers in the parentheses are the numbers that should be counted when we calculate the inverse number.
    Now we need to merge these two arrays into one sorted array. The first element to be put into the sorted destination array is the "1" in the first array.

     1                  4(1) 6(1,4) 8
                      2 5(2) 7(2,5) 9               merged elements in the 2nd array = ()
    

    The second element to merge is the "2" in the second array:

     1 2                4(1) 6(1,4) 8
                        5(2) 7(2,5) 9               merged elements in the 2nd array = (2)
    

    The third element to merge is the "4" in the first array:

     1 2 4(1,2)              6(1,4) 8
                        5(2) 7(2,5) 9               merged elements in the 2nd array = (2)
    

    When we merge the "4(1)", we found that "4" is actually greater than all merged elements in the second array (i.e. [2]). Therefore, we also need to consider those elements. Therefore, the numbers in the parenthese of 2 become (1)+(2) = (1,2). Next step:

     1 2 4(1,2) 5(2)         6(1,4) 8
                             7(2,5) 9               merged elements in the 2nd array = (2,5)
    

    Next (add the inverse number of element "6" by 2)

     1 2 4(1,2) 5(2) 6(1,4,2,5)     8
                             7(2,5) 9               merged elements in the 2nd array = (2,5)
    

    So and so forth, finally reach

     1 2 4(1,2) 5(2) 6(1,4,2,5) 7(2,5) 8(2,5,7) 9
                                                    merged elements in the 2nd array = (2,5,7,9)
    

    Additionally, when we need to count the inverse number, we do not need to record the exact elements, we only need to record the numbers. So, we can use a variable to record the number of "merged elements in the 2nd array" (for example, semilen in the code beneath) and the number of smaller elements of each element (for example, results[idx] in the code beneath).

    Complexities:

    • Time: O(n log n)

    • Space: O(n)

    C++ Accepted Code:

    class Solution {
    protected:
        void merge_countSmaller(vector<int>& indices, int first, int last, 
                                vector<int>& results, vector<int>& nums) {
            int count = last - first;
            if (count > 1) {
                int step = count / 2;
                int mid = first + step;
                merge_countSmaller(indices, first, mid, results, nums);
                merge_countSmaller(indices, mid, last, results, nums);
                vector<int> tmp;
                tmp.reserve(count);
                int idx1 = first;
                int idx2 = mid;
                int semicount = 0;
                while ((idx1 < mid) || (idx2 < last)) {
                    if ((idx2 == last) || ((idx1 < mid) &&
                           (nums[indices[idx1]] <= nums[indices[idx2]]))) {
    					tmp.push_back(indices[idx1]);
                        results[indices[idx1]] += semicount;
                        ++idx1;
                    } else {
    					tmp.push_back(indices[idx2]);
                        ++semicount;
                        ++idx2;
                    }
                }
                move(tmp.begin(), tmp.end(), indices.begin()+first);
            }
        }
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> results(n, 0);
            vector<int> indices(n, 0);
            iota(indices.begin(), indices.end(), 0);
            merge_countSmaller(indices, 0, n, results, nums);
            return results;
        }
    };

  • 1
    T

    Hi,
    Thanks for sharing your solution.

    How did you come up with the idea "MergeSort-based solution is a standard way to solve problems related to inverse numbers."? Did you summarize it by yourself or you find it somewhere else?


  • 2

    Hi, tang. Merge sort is indeed a standard way to deal with problems related to the inverse number calculation. You can find more details in the following link:

    http://www.geeksforgeeks.org/counting-inversions/


  • 0
    G

    thanks for your sharing! very easy to understand!


  • -1
    X

    Thanks for your detailed explanation!


  • 2
    L

    It's very hard for me to understand the "nums[indices[indx]]", what does this mean?
    why using an indices?


  • 2

    I have to say it is really hard to understand, comparing with the geekforgeeks


  • 0
    X
    This post is deleted!

  • 0
    A

    Thanks for sharing.
    some questions.
    is it possible not to use index vector?
    for temp vector, why first reserve space and then move to index vector?

    thanks


  • 0
    F

    @leetchunhui indices stores the original indices of the elements and is sorted using merge sort while nums is not sorted. After sorting, i'th element in indices indices[i] corresponds to the i'th smallest element's original index in nums. If we have nums also sorted together with indices which consumes extra n space, then the previous nums[index[i]]=nums[i]. indices is used because the result needs to be presented in the original indices order.


  • 0
    M

    @zhiqing_xiao thanks for sharing. Revised the code a little bit:

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> res(n, 0), indexes(n, 0);
            for(int i = 0; i < n; ++i) indexes[i] = i;
            countSmaller(res, indexes, nums, 0, n);
            return res;
        }
        
        void countSmaller(vector<int>& res, vector<int>& indexes, vector<int>& nums, int first, int last){
            int len = last - first;
            if(len <= 1) return;
            
            int mid = first + len / 2;
            countSmaller(res, indexes, nums, first, mid);
            countSmaller(res, indexes, nums, mid, last);
            
            vector<int> updated;
            updated.reserve(len);        
            int p1 = first, p2 = mid, cnt = 0;
            while(p1 < mid || p2 < last){
                if(p2 == last || (p1 < mid && nums[indexes[p1]] <= nums[indexes[p2]])){ 
                    updated.push_back(indexes[p1]);
                    res[indexes[p1]] += cnt;
                    ++p1;
                }else{
                    updated.push_back(indexes[p2]);
                    ++cnt, ++p2;
                }
            }
            move(updated.begin(), updated.end(), indexes.begin() + first);
        }
    };
    

Log in to reply
 

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