题目解析
这大概是第一章中最难的一道题了吧,对于算法初学者来说,我第一次看视频还是看代码都是一脸懵;代码量也比平常多了一倍
学习难点的建议(写给自己)
1:先搜一些题解,然后根据题解写成自己喜欢格式的代码,这样下来会对题解的脉络有一个清晰的认识
2:然后在逐一攻破自己不懂的点,可以拿数据来实验一下,走一遍流程,思路就很清晰了
先上java模板
List<Integer> alls; // 存储所有待离散化的值
Collections.sort(alls); // 将所有值排序
private static List<Integer> unique(List<Integer> alls){ //去掉重复元素
int j = 0; //i指针循环整个数组 j指针设置不重复的值 然后重复的值就被顶到j后面了
for(int i = 0; i < alls.size(); i ++){
if(i == 0 || alls.get(i) != alls.get(i-1)){
alls.set(j++,alls.get(i));
}
}
return alls.subList(0,j);
}
// 二分求出x对应的离散化的值
private static int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
java代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
private static int N = 300010; //alls中存储的是x,l,r 1≤n,m≤100000 n+2m=300010;
private static List<int[]> add = new ArrayList<>(); //add集合存放插入操作,x,c
private static List<int[]> query = new ArrayList<>(); //query数组存放询问操作,l,r
private static List<Integer> alls = new ArrayList<>(); //用来存储x,l,r
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] a = new int[N]; //根据离散化后的坐标插入的值
int[] s = new int[N]; //前缀和数组
for(int i = 0; i < n; i ++){
int x = in.nextInt();
int c = in.nextInt();
add.add(new int[]{x,c}); //[1,2],[3,6],[7,5]
alls.add(x);
}
for(int i = 0; i < m; i ++){
int l = in.nextInt();
int r = in.nextInt();
query.add(new int[]{l,r}); //[1,3],[4,6],[7,8]
alls.add(l);
alls.add(r);
}
//alls数组此时是1,3,7,1,3,4,6,7,8 下面就是排序,去重
Collections.sort(alls); //排序:113346778
List<Integer> unique = unique(alls); //去重:134678 离散化完毕
for(int[] t:add){ //add [1,2],[3,6],[7,5]
int x = find(t[0]); //1 返回1
int c = t[1]; //2
a[x] = a[x] + c; //026005 a[1] = 2 a[2] = 6 a[5] = 5
}
for(int i = 1; i < a.length; i ++) s[i] = s[i-1] + a[i]; //前缀和
for(int[] t : query){
int l = find(t[0]);
int r = find(t[1]);
System.out.println(s[r] - s[l-1]);
}
}
private static List<Integer> unique(List<Integer> alls){ //去掉重复元素
int j = 0; //i指针循环整个数组 j指针设置不重复的值 然后重复的值就被顶到j后面了
for(int i = 0; i < alls.size(); i ++){
if(i == 0 || alls.get(i) != alls.get(i-1)){
alls.set(j++,alls.get(i));
}
}
return alls.subList(0,j);
}
private static int find(int x){ //二分求出x对应离散化后的坐标 输入x,l,r 找到x,l,r离散化后的位置
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
}
解析
1;什么是离散化
是把一个有序的分布稀疏的数组 映射 到相邻的数组元素中;这样减少了空间复杂度和时间复杂度
2:离散化在本题的操作步骤
1:开辟一个新的集合alls,里面存储的是x,l,r 也就是所有的坐标 //(1,3,7,1,3 4,6 7,8 )
2: 排序 ;因为离散化是有序的数组来映射,所以需要排序 //113346778
3:去重,去除alls集合中所有的重复元素 //134678
3:分析去重方法的思想
private static List<Integer> unique(List<Integer> alls){ //去掉重复元素
int j = 0; //i指针循环整个数组 j指针设置不重复的值 然后重复的值就被顶到j后面了
for(int i = 0; i < alls.size(); i ++){
if(i == 0 || alls.get(i) != alls.get(i-1)){
alls.set(j++,alls.get(i));
}
}
return alls.subList(0,j);
}
1:首先的话,是用到了双指针算法,声明i,j两个指针,i指针循环整个alls数组,j指针用来设置不重复的值;
2:for循环每走一次,i指针就会向前走一步,只有当没有出现不重复的值的时候,j指针才会向前走,如果出现了重复的元素,j指针就不会走;所以j走过的路程就全是不重复的,然后重复的值就被顶到j后面了;所以我们用subList截取了数组(0,j),剩下重复的元素就会被弃用
3:那什么时候是不重复的呢,需要满足两个条件
因为alls集合已经排过序了,所以如果有重复的元素那么肯定是按在一起的 比如说:1223334
所以只要当前元素不等于前一个元素,那么就是不重复的;也就是alls.get(i) != alls.get(i-1)
然后再读取第一个数字的时候,也肯定是不重复的,但是在alls.get(0) != alls.get(-1)就会出现边界问题,所以有了i==0这个条件
4:为什么N = 300010;
1:N指的是声明的是最大数组的大小,这个题最大的数组是aiis,存储的是x,l,r;然后x,l,r的个数有1≤n,m≤100000个,所以大小是n + 2m = 300000
2:为什么要加10呢
这个是y总的一个习惯,是为了处理边界问题,预防数组越界异常,原本的话,+1也是可以的,但是加10会更保险;
虽然这样浪费了空间, 但是算法题主要看的是能不能ac,时间复杂度是不是小,是可以牺牲空间换时间的;
写工程的话就不必这么做了
5:add和query集合存储的是什么;
我在学习的时候,一直弄不懂add和query集合存储的是什么,pairs到底是个啥玩意,为什么要这么做;
我这里的话用的是int[] 代替了pairs,这样就很明显了,集合里面套着一个数组
add集合中存储的就是x,c 题目为例:[1,2],[3,6],[7,5]
query集合存储的就是l,r 题目为例:[1,3],[4,6],[7,8]
这样的话是把[x,c]一起存储,[l,r]一起存储,用的时候好用
6:二分解析
private static int find(int x){ //二分求出x对应离散化后的坐标 输入x,l,r 找到x,l,r离散化后的位置
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
离散化后的数组:alls:134678
输入:x,l,r坐标 比如:输入x = 1
输出:x,l,r在离散化数组中的位置 输出l + 1 = 0 + 1 = 1
所以二分的作用很明显了,就是用来找x,l,r在离散化数组中的位置
通过输入x我们可以进行插入操作,插入到a[]数组中
通过输入l,r我们可以求区间和
因为alls数组就是用x,l,r组成的,所以一定能找到对应的值
因为考虑到了前缀和来求区间和,所以映射到了1,2,3,4,....的序列,写成了 l + 1
7:a[]数组存储的是什么;
a[]在离散化后的坐标的位置,插入了c;而代替了之前在x的位置插上c;这样就达到了我们的目的,缩小了数据范围,减少了空间复杂度
2021.1.1.0.30 完 祝大家新年快乐!祝y总的Acwing越来越火热!加油..
其实list去重可以用 “list= list.stream().distinct().collect(Collectors.toList())”; 可以省下一大段代码