本帖最后由 wuxin0011 于 2024-9-24 21:24 编辑
本帖最后由 wuxin0011 于 2024-9-24 21:20 编辑
本帖最后由 wuxin0011 于 2024-9-24 21:14 编辑
打卡
计算右侧小于当前元素的个数
这道题如果想到相关数据结构就简单了
相关技巧
-
离散化 这种技巧很常见 由于只关心大小 而不关心具体值，往往通过排序 + 二分查找排名 用排名排名代替具体数值，这种方式就是离散化。 查询复杂度为 log(n), 这个过程也可以预处理，用 hash 加速查找，能够优化到 O(1)，如果值不太大，在1e6范围内 可以替代因此可以用 数组代替 hash 表 查询性能为 O(1) ,数组效率常数远小于hash表 性能更优,
-
树状数组 这题可以说专门为这个数据结构准备的 累加和查询，本题只需要统计个数，因此 每次在对应位置更新 +1 ，题目要求统计右侧小于该位置数值个数，可以从右到左遍历
class Solution {
public List<Integer> countSmaller(int[] nums) {
int[] a = Arrays.copyOf(nums,nums.length);
Arrays.sort(a);
int size = 1;
int n = a.length;
for(int i = 1;i < n;i++) {
if(a[size - 1] != a[i]) {
a[size++] = a[i];
}
}
// System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
int[] ans = new int[n];
Fenwick f = new Fenwick(n);
for(int i = n - 1;i >= 0;i--) {
int val = lowerbound(a,size,nums[i]);
int cnt = f.sums(val - 1);
ans[i] = cnt;
f.add(val,1);
}
List<Integer> ls = new ArrayList<>();
for(int val : ans) ls.add(val);
return ls;
}
public static int lowerbound(int[] a,int size,int t) {
int l = 0,r = size - 1;
while(l <= r) {
int mid = l + ((r - l)>> 1);
if(a[mid]>=t)r = mid - 1;
else l = mid + 1;
}
return l;
}
public static class Fenwick {
int n;
int[] tree, diff, a;
public Fenwick(int[] a) {
this.n = a.length;
this.tree = new int[n + 1];
this.diff = new int[n + 1];
this.a = a;
}
public Fenwick(int n) {
this.n = n;
this.tree = new int[n + 1];
}
public void init() {
for (int i = 0; i < n; i++) {
this.add(i, a[i]);
}
}
public int lowbit(int i) {
return i & -i;
}
public void add(int i, int val) {
int v = val;
if (diff != null) {
v = val - this.diff[i];
this.diff[i] = v;
}
i++;
while (i <= n) {
tree[i] += v;
i += lowbit(i);
}
}
private int sums(int i) {
int s = 0;
i++;
while (i > 0) {
s += tree[i];
i -= lowbit(i);
}
return s;
}
public int sums(int l, int r) {
if (l < 0 || r > n || l > r) {
return 0;
}
return sums(r) - sums(l - 1);
}
}
}
提交地址
时间复杂度为 nlog(n) [ 排序 nlog(n) + 二分查找 nlog(n) + 树状数组求和 nlog(n)]
空间复杂度为 o(n) (拷贝数组o(n) + 创建树状数组o(n) ]
用数组代替map优化后代码
class Solution {
static int N = (int)1e4 + 10;
public List<Integer> countSmaller(int[] nums) {
int[] a = Arrays.copyOf(nums,nums.length);
Arrays.sort(a);
int size = 1;
int n = a.length;
int max = a[n-1];
max++;
// 由于存在负数 -1e4, 因此需要 + 一个常量拓展数组 防止下标越界
int[] map = new int[max + N];
map[a[0] + N] = 0;
for(int i = 1;i < n;i++) {
if(a[size - 1] != a[i]) {
a[size++] = a[i];
map[a[size-1] + N] = i;
}
}
// System.out.printf("size = %d,a = %s\n",size,Arrays.toString(a));
int[] ans = new int[n];
Fenwick f = new Fenwick(n);
for(int i = n - 1;i >= 0;i--) {
// int val = lowerbound(a,size,nums[i]);
int val = map[nums[i] + N];
int cnt = f.sums(val - 1);
ans[i] = cnt;
f.add(val,1);
}
List<Integer> ls = new ArrayList<>();
for(int val : ans) ls.add(val);
return ls;
}
public static int lowerbound(int[] a,int size,int t) {
int l = 0,r = size - 1;
while(l <= r) {
int mid = l + ((r - l)>> 1);
if(a[mid]>=t)r = mid - 1;
else l = mid + 1;
}
return l;
}
public static class Fenwick {
int n;
int[] tree, diff, a;
public Fenwick(int[] a) {
this.n = a.length;
this.tree = new int[n + 1];
this.diff = new int[n + 1];
this.a = a;
}
public Fenwick(int n) {
this.n = n;
this.tree = new int[n + 1];
}
public void init() {
for (int i = 0; i < n; i++) {
this.add(i, a[i]);
}
}
public int lowbit(int i) {
return i & -i;
}
public void add(int i, int val) {
int v = val;
if (diff != null) {
v = val - this.diff[i];
this.diff[i] = v;
}
i++;
while (i <= n) {
tree[i] += v;
i += lowbit(i);
}
}
private int sums(int i) {
int s = 0;
i++;
while (i > 0) {
s += tree[i];
i -= lowbit(i);
}
return s;
}
public int sums(int l, int r) {
if (l < 0 || r > n || l > r) {
return 0;
}
return sums(r) - sums(l - 1);
}
}
}
提交地址
时间复杂度为 nlog(n) [ 排序 nlog(n) + 查找 o(1) + 树状数组求和 nlog(n)]
空间复杂度为 o(max + 1e4 + 10) (拷贝数组o(n) + 创建树状数组o(n) ] max为数组最大值
照妖镜