315、计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
题解
求逆序数问题，可以用归并排序统计总数。
1、暴力
时间复杂度：$O(n^2)$，显然超时！！！
class Solution {
public List<Integer> countSmaller(int[] nums) {
// 暴力
int len = nums.length;
int[] count = new int[len];
for (int i = len - 1;i >= 0;i--) {
count[i] = 0;
// 存在重复计算
for (int j = len - 1;j > i;j--) {
if (nums[i] > nums[j]) {
count[i]++;
}
}
}
ArrayList<Integer> res = new ArrayList<>();
for (int c : count) {
res.add(c);
}
return res;
}
}
2、离散化树状数组
树状数组
树状数组 是一种可以动态维护序列前缀和的数据结构，它的功能是：
- 单点更新
update(i,v)：把序列i的位置的数加上一个值v，在该题中v = 1 - 区间查询
query(i)：查询序列[1...i]区间的区间和，即i位置的前缀和
修改和查询的时间代价是$O(logn)$，其中n为需要维护前缀和的序列长度
转化成动态维护前缀和问题
前缀和counnt[i]表示：nums[i]之后小于nums[i]数量总和
离散化优化空间
- 值域映射
class Solution {
private int[] c;
private int[] a;
public List<Integer> countSmaller(int[] nums) {
List<Integer> resultList = new ArrayList<Integer>();
discretization(nums);
init(nums.length + 5);
for (int i = nums.length - 1;i >= 0;--i) {
int id = getId(nums[i]);
resultList.add(query(id-1));
update(id);
}
Collections.reverse(resultList);
return resultList;
}
// 初始化前缀和
private void init(int length) {
c = new int[length];
Arrays.fill(c,0);
}
private int lowBit(int x) {
// -x <==> (~x + 1)
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) {
// hash表去重
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);
}
private int getId(int x) {
return Arrays.binarySearch(a,x) + 1;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
