题目地址：（https://leetcode.cn/problems/count-of-smaller-numbers-after-self）

题目描述

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

示例1

输入：nums = [5,2,6,1]
输出：[2,1,1,0]

示例2

输入：nums = [-1]
输出：[0]

示例2

输入：nums = [-1，-1]
输出：[0，0]

数据约束

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

思路

首先根据题意可知，需要的答案是每一位后面又几个数字小于这个数据。最简单直接的想法就是遍历两次，第一次遍历找点，第二次遍历找点之后的数据然后去比对是否小于，如果小于则记录进去，但是可以看到nums.length最大可达10^5那么直接求需要较多的时间。那么还有一种方法就是树状数组。对于树状数组来说每次查找的区间长度不再是1而是2的k次方，既每一跳可以代表一个大区间。对于一个长度为8的数组。大体结构如图

那么问题是怎么确定哪些区间有多长呢？介于树状数组的区间长度是2的k次方，那么使用索引的二进制里面的1最好。因此选用索引二进制码中的第一个1作为长度，对于3就是1对于6就是2。但是0除了符号位可能为1以为其他位数不肯为1所以索引需要从1开始，到长度截止既1~N。对于求第一个1只需要让一个数与其复数求&即可。

	private int lowbit(int x) {
		return x&-x;
	}
1
2
3

对于修改，子集改了那么对于一个包含这个子集的集合来说肯定也是需要更改的

	private void update(int pos,int val) {
		while (pos < c1.length) {
			c1[pos]+=val;
			pos += lowbit(pos);
		}
	}
1
2
3
4
5
6

对于查询，树状数组维护的是一个区间的值，而再查找的时候查找返回的数据是从1到查找位置之前的值

	private int query(int pos) {
		int ans = 0;
		while (pos > 0) {
			ans += c1[pos];
			pos -= lowbit(pos);
		}
		return ans;
	}
1
2
3
4
5
6
7
8

对于这个题目可以发现一个问题，数组的长度和数组的内部数据并不挂钩，既可以有像[10000,20000,0,-55,1,1,2,3]这样的数组，可以看到数组的长度不长，但是如果需要保存每一个值的话不仅需要将负值转化为正值同时有大量无效的区间根本不会被利用，这就导致了大量的内存的浪费。对于这种方法可以选择以数据在数组中"第几大"作为索引，那么无论数组里面的数数值多大，对于第几大来说始终是一个不会大于数组长度的值。那么树状数组的大小就可以得到很大的压缩。同时既然是求第几大那么重复的数据也可以不要了，毕竟并列只需要一个来表示一下既可以了。那么就可以使用HashSet进行优化。优化函数就可以是

	private void hash(int[] nums) {
		HashSet<Integer> set = new HashSet<>();
		for (int num : nums) {
			set.add(num);
		}
		a1 = new int[set.size()];
		int index = 0;
		for (int num : set) {
			a1[index++] = num;
		}
		Arrays.sort(a1);
	}
1
2
3
4
5
6
7
8
9
10
11
12

哈希优化之后就简单了，直接使用树状数组进行处理，插入之前查询并累加，然后再将数据插入进入即可。就可以得到最终的结果了。

代码

private int[] a1;
	private int[] c1;

	private void hash(int[] nums) {
		HashSet<Integer> set = new HashSet<>();
		for (int num : nums) {
			set.add(num);
		}
		a1 = new int[set.size()];
		int index = 0;
		for (int num : set) {
			a1[index++] = num;
		}
		Arrays.sort(a1);
	}

	private int getIndex(int x) {
		return Arrays.binarySearch(a1, x) + 1;
	}

	private int lowbit(int x) {
		return x & -x;
	}

	private void add(int pos) {
		while (pos < c1.length) {
			c1[pos]++;
			pos += lowbit(pos);
		}
	}

	private int query(int pos) {
		int ans = 0;
		while (pos > 0) {
			ans += c1[pos];
			pos -= lowbit(pos);
		}
		return ans;
	}

	public List<Integer> countSmaller(int[] nums) {
		List<Integer> ans = new ArrayList<>();
		hash(nums);
		c1 = new int[nums.length];
		for (int i = nums.length - 1; i >= 0; i--) {
			int index = getIndex(nums[i]);
			ans.add(query(index - 1));
			add(index);
		}
		Collections.reverse(ans);
		return ans;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52