LeetCode [315] Count of Smaller Numbers After Self

 315. Count of Smaller Numbers After Self

Hard

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

 

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

 

Constraints:

• 0 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

//C++: 680ms  Sort from the end
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, 0);
        for(int i=n-2; i>=0; --i){
            int t = nums[i];
            int j;
            for(j = i+1; j<n; ++j){
                if(nums[j]>=t) break;
            }
            nums.insert(nums.begin()+j, t);
            nums.erase(nums.begin()+i);
            ret[i] = j-i-1;
        }
        return ret;
    }
};
]]></script>
<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 104ms  binary search
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {     
     int n = nums.size();
     vector<int> ret(n,0);
     for(int i=n-2; i>=0; --i){
         int l = i+1, r = n-1, m;
         while(l<=r){
          m = (l+r)/2;
          if((nums[m]>=nums[i] && nums[m-1]<nums[i])){
              break;
          }else if(nums[m]>=nums[i]){
              r = m-1;
          }else{
              l = m+1;
          }
         }
         if(r<=i) m = i+1;
         if(l>=n) m = n;
         nums.insert(nums.begin()+m, nums[i]);
         nums.erase(nums.begin()+i);
         ret[i] = m-(i+1);
     }
 return ret;
    }
};
]]></script>
<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 100ms merge sort
class Solution {
    vector<int> numbers;
    vector<int> ret;
public:

    vector<int> merge(vector<int> leftIndices, vector<int> rightIndices){
        int szl = leftIndices.size();
        int szr = rightIndices.size();
        int i = 0, j = 0, cnt = 0;
        vector<int> sortedIndices;
        while(i<szl && j<szr){
            if(numbers[leftIndices[i]]<=numbers[rightIndices[j]]){
                sortedIndices.push_back(leftIndices[i]);
                ret[leftIndices[i]] += cnt;
                i++;
            }else{
                sortedIndices.push_back(rightIndices[j]);
                j++;
                cnt++;
            }
        }
        while(i<szl){
            sortedIndices.push_back(leftIndices[i]);
            ret[leftIndices[i]] += cnt;
            i++;
        }
        while(j<szr){
            sortedIndices.push_back(rightIndices[j]);
            j++;
        }
        return sortedIndices;
    }
    void divide(vector<int> &indices){
        int n = indices.size();
        if(n<2) return;
        int mid = n/2;
        vector<int> left(indices.begin(), indices.begin()+mid);
        vector<int> right(indices.begin()+mid, indices.end());
        divide(left);
        divide(right);
        indices = merge(left, right);
    }

    vector<int> countSmaller(vector<int>& nums) {
        numbers = nums;
        int sz = nums.size();
        ret.resize(sz, 0);
        vector<int> indices(sz);
        for(int i=0; i<sz; ++i){
            indices[i] = i;
        }
        divide(indices);
        return ret;
    }
};

//Java
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int v:nums) list.add(v);
        List<Integer> counts = new ArrayList<Integer>(n);
        for(int i=0; i<n; ++i) counts.add(0);
        //sort nums from right to left;
        for(int i=n-2; i>=0; --i){
            int l = i+1, r = n-1;
            while(l<r){
                int m = (l+r)/2;
                if(list.get(m)<list.get(i)){
                    l = m+1;
                }else{
                    r = m;
                }
            }
            if(list.get(l)<list.get(i)){
                l = n;
            }
            list.add(l, list.get(i));
            list.remove(i);
            counts.set(i, l-i-1);
        }
        return counts;
    }
}