O(n*log(n)) solution using divide and conquer (> 75% of accepteds)


  • 0
    A

    My solution uses divide and conquer to generate a running time of O(n*log(n)). It was rated as better that 75% of all the other solutions.

    The key thing here is to note that in the merge step, we also keep track of the count of number smaller than the current index on the right half of the items being merged. The rest of the algorithm follows the standard merge sort technique.

    #include <iostream>
    #include <vector>
    #include <functional>
    
    using namespace std;
    
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<CountData> countNums;
            countNums.reserve(nums.size());
    
            if (nums.size() > 0)
            {
                vector<CountData> mergeData;
                mergeData.reserve(nums.size());
    
                int index = 0;
                for (auto num : nums)
                {
                    countNums.push_back(CountData(num, index++, 0));
                }
    
                MergeAndCountHelper(countNums, 0, nums.size()-1, mergeData);
            }
            
            vector<int> returnValues(nums.size(), 0);
    
            for (auto& countData: countNums)
            {
                returnValues[countData.originalIndex] = countData.count;
            }
    
            return returnValues;
        }
    
    private:
        struct CountData
        {
            CountData(int inValue, int origIndex, int inCount):
                value(inValue),
                originalIndex(origIndex),
                count(inCount)
            {
            }
    
            int value;
            int originalIndex;
            int count;
        };
    
        void MergeAndCountHelper(vector<CountData>& numbers, unsigned int start, unsigned int end, vector<CountData>& mergeData)
        {
            if (start != end)
            {
                auto mid = start + (end - start) / 2;
    
                MergeAndCountHelper(numbers, start, mid, mergeData);
                MergeAndCountHelper(numbers, mid + 1, end, mergeData);
    
                unsigned int left = start, right = mid + 1, curIndex = 0;
    
                while (left <= mid || right <= end)
                {
                    if (left <= mid && (right > end || numbers[left].value <= numbers[right].value))
                    {
                        mergeData[start + curIndex] = numbers[left];
                        mergeData[start + curIndex].count += (right-mid-1);
                        left++;
                    }
                    else if (right <= end && (left > mid || numbers[right].value < numbers[left].value))
                    {
                        mergeData[start + curIndex] = numbers[right];
                        right++;
                    }
    
                    curIndex++;
                }
    
                memcpy(&numbers[start], &mergeData[start], sizeof(CountData)*(end - start + 1));
            }
        }
    };

Log in to reply
 

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