LeetCode

[LeetCode]315. Count of Smaller Numbers After Self

后面比本身小的个数

Posted by JinFei on April 1, 2020

题目描述

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].

Example1:

  Input: [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.

解题思路

参考
首先可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，
那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for(int i = nums.size() - 1; i >= 0; i--){
            int left = 0;
            int right = t.size();
            while(left < right){
                int mid = (left + right) / 2;
                if(t[mid] >= nums[i]){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
            res[i] = right;
            t.insert(t.begin() + right, nums[i]);
        }
        return res;
    }
};