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
计算右侧小于当前元素的个数。题意是给一个数组，请你返回一个等长的list，表示当前位置的右侧小于nums[i]的元素个数。
暴力解是O(n^2)的复杂度，肯定是不行的。我这里暂时给出一个二分法的思路。创建一个跟input数组等长的arr数组记录结果，同时再创建一个空的list做插入排序。数组从右往左扫描，对于每一个元素，我们把他插入list一个合适的位置，使得list最后依然是有序的。这个插入的动作，比较高效的做法就是用二分。这个元素当时被插入list的index，同时也是这个元素的右侧有多少个元素小于他自己的个数。
时间O(nlogn)
空间O(n)
Java实现
1 class Solution {
2 public List<Integer> countSmaller(int[] nums) {
3 // 返回结果
4 List<Integer> res = new ArrayList<>();
5 // 数组长度为0，直接返回
6 if (nums.length == 0) {
7 return res;
8 }
9 // 为了提高效率，新建一个数组型的返回结果
10 int[] arr = new int[nums.length];
11 // 新建一个list，用于排序
12 List<Integer> list = new ArrayList<>();
13 // 从数组最后一位开始向前循环
14 for (int i = nums.length - 1; i >= 0; i--) {
15 // 当前数字
16 int num = nums[i];
17 // 将当前数字插入到新建list中
18 // 使用二分查找找到插入位置
19 int left = 0;
20 int right = list.size() - 1;
21 while (left <= right) {
22 int mid = (left + right) / 2;
23 if (num <= list.get(mid)) {
24 right = mid - 1;
25 } else {
26 left = mid + 1;
27 }
28 }
29 // 将当前数字插入到相应位置，保证list升序排列
30 list.add(left, num);
31 // 当前位置前所有数字均小于当前数字，将个数加入返回结果
32 arr[i] = left;
33 }
34 // 将list转化为数组
35 for (int count : arr) {
36 res.add(count);
37 }
38 return res;
39 }
40 }
相关题目
315. Count of Smaller Numbers After Self
1365. How Many Numbers Are Smaller Than the Current Number