315. 计算右侧小于当前元素的个数（每日一题）

题目

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
难度：困难

思路

1.看了之后，第一反应是暴力法两层循环，时间复杂度O(n^2)，如果这么做只够简单难度，肯定要求的是更优解法。
2.由于用的是IDEA的leetcode插件，会有分类的提示，// Related Topics 排序树状数组线段树二分查找分治算法二分查找的目的是为了当前元素右侧是有序的，如果从左开始，每次都要完整的重新维护一次右侧元素，如果从右侧开始，相当于每次新增一个元素到有序序列中，res的最右第一个一定是0(因为最后一个元素右侧没有新元素)，此处尝试用java提供的TreeMap完成。
3.python有神奇的魔法bisect，按上面的思路拿来试试

解法

1.两层循环，结果是16个测试用例，最后一个超时挂掉了。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class countSmaller {
    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        List<Integer> res = new ArrayList<>(Collections.nCopies(len, 0));
        for (int i = 0; i < len - 1; i++) {
            int count = 0;
            for (int j = i + 1; j < len; j++) {
                if (nums[j] < nums[i]) {
                    count++;
                }
            }
            res.set(i, count);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

2.TreeMap,出乎意料，第16个测试用例又超时挂掉了。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

//leetcode submit region begin(Prohibit modification and deletion)
class countSmaller {
    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        List<Integer> res = new ArrayList<>(Collections.nCopies(len, 0));

        if (len < 1) {
            return res;
        }

        TreeMap<Integer, Integer> treeMap = new TreeMap<>();

        for (int i = len - 2; i >= 0; i--) {
            int key = nums[i + 1];
            if (treeMap.containsKey(key)) {
                treeMap.put(key, treeMap.get(key) + 1);
            } else {
                treeMap.put(key, 1);
            }

            Map<Integer, Integer> map = treeMap.headMap(nums[i]);
            int count = 0;
            for (Integer value : map.values()) {
                count += value;
            }

            res.set(i, count);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

3.python的bisect，然后就过了。。。。

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        num_length = len(nums)
        if not nums:
            return []

        res = [0]*num_length
        sorted_nums = []
        for i in range(len(nums)-1, -1, -1):
            idx = bisect.bisect_left(sorted_nums, nums[i])
            sorted_nums.insert(idx, nums[i])
            res[i] = idx
        return res