1.题目

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：
输入：nums = [-1]
输出：[0]

示例 3：
输入：nums = [-1,-1]
输出：[0,0]

提示：
1 <= nums.length <= 10⁵
-104 <= nums[i] <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，即使用 2 层 for 循环来穷举并用 res 来保存答案即可，不过该方法的时间复杂度较高，为 O(n²)，在 LeetCode 中提交时会出现“超过时间限制”的提示！

（2）树状数组
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {public List<Integer> countSmaller(int[] nums) {ArrayList<Integer> res = new ArrayList<>();int n = nums.length;for (int i = 0; i < n; i++) {int cnt = 0;for (int j = i + 1; j < n; j++) {if (nums[i] > nums[j]) {cnt++;}}res.add(cnt);}return res;}
}

//思路2————树状数组
class Solution {private int[] c;private int[] a;public List<Integer> countSmaller(int[] nums) {List<Integer> resultList = new ArrayList<Integer>(); discretization(nums);c = new int[nums.length];for (int i = nums.length - 1; i >= 0; --i) {int id = Arrays.binarySearch(a, nums[i]) + 1;resultList.add(query(id - 1));update(id);}Collections.reverse(resultList);return resultList;}private int lowBit(int x) {return x & (-x);}private void update(int pos) {while (pos < c.length) {c[pos] += 1;pos += lowBit(pos);}}private int query(int pos) {int ret = 0;while (pos > 0) {ret += c[pos];pos -= lowBit(pos);}return ret;}private void discretization(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int num : nums) {set.add(num);}int size = set.size();a = new int[size];int index = 0;for (int num : set) {a[index++] = num;}Arrays.sort(a);}
}