题目地址：（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

思路

First of all, according to the meaning of the title,The required answer is that several numbers after each digit are less than this data.The simplest and most straightforward idea is to traverse twice,The first traversal to find the point,The second traversal to find the data after the point and then to compare whether it is less than,If it is less than it is recorded,但是可以看到nums.length最大可达10^5Then it takes more time to ask directly.Then there is another way is the tree array.For tree-like arrays, the interval length for each lookup is no longer the same1而是2的k次方,That is, each hop can represent a large interval.对于一个长度为8的数组.大体结构如图

The question then is how to determine which intervals are how long？The length of the interval between the tree-like arrays is 2的k次方,Then use the index inside the binary1最好.Therefore, the first one of the indexed binary codes is chosen1作为长度,对于3就是1对于6就是2.但是0Except the sign bit may be1I thought other digits would not do it1So the index needs to start from1开始,to the length cutoff both1~N.For the first one1Just ask a number to find its complex number&即可.

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

对于修改,If the subset is changed, then a set that contains this subset must also need to be changed

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

对于查询,The tree-like array maintains an interval of values,When searching again, the data returned by the search is from1The value before the lookup position

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

A problem can be found on this subject,The length of the array is not linked to the internal data of the array,can have something like[10000,20000,0,-55,1,1,2,3]这样的数组,You can see that the length of the array is not long,But if you need to save every value, you not only need to convert negative values ​​to positive values, but also a large number of invalid intervals will not be used at all,This results in a lot of wasted memory.For this method you can choose to have the data in an array"第几大"作为索引,So no matter how big the number in the array is,For the largest number, it is always a value that is not greater than the length of the array.Then the size of the tree array can be greatly compressed.At the same time, since it is asking for the largest number, then the repeated data can be omitted,After all, juxtaposition only needs one to express it.那么就可以使用HashSet进行优化.The optimization function can be

	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);
	}

Simple after hash optimization,Direct use of tree arrays for processing,Query and accumulate before inserting,Then insert the data into it.You can get the final result.

代码

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;
	}