离散化与区间合并
离散化
什么是离散化？ 当题目的数值范围非常大（例如坐标在 -10⁹ ~ 10⁹），但实际用到的数值个数很少（例如只有 10⁵ 个）时，无法开一个覆盖整个值域的数组。离散化把所有”实际用到”的数值排序去重后，映射到从 1 开始的连续下标上，之后就可以像处理小数组一样处理它们。
保序离散化的三步：
- 收集： 把所有需要离散化的数值（加点位置、询问端点等）全部放进一个数组 alls；
- 排序去重： 排序后把重复元素去掉（见下面”数组排序去重”代码，去重函数返回新长度 len）；
- 二分查找映射： 查询数值 x 时，在 alls 中二分出 x 的下标（一般 +1 使下标从 1 开始），这个下标就是 x 离散化后的”新坐标”。
为什么下标要从 1 开始？ 因为后续通常要配合前缀和数组 s 使用，s[0] = 0 可以省去左端点越界的特判，与”前缀和”篇的做法保持一致。
数组排序去重
import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { int[] arr = {1,2,1,3,2,5,6,4,1,9,2,2}; //排序 Arrays.sort(arr); int len = unique(arr); System.out.println(len); //截取非重复部分 int[] b = Arrays.copyOf(arr,len); for (int i = 0; i < b.length; i++) { System.out.print(b[i] + " "); }
} public static int unique(int[] a){ int j = 0; //满足的条件 //1,数组中的第一个元素 //2，a[i] != a[i-1] for (int i = 0; i < a.length; i++) { if(i == 0 || a[i] != a[i-1]) a[j++] = a[i]; } return j; }}双指针去重的原理： 数组已有序，相等的元素一定相邻。慢指针 j 指向”下一个要写入的位置”，快指针 i 从头扫到尾；a[i] != a[i-1]（或 i == 0）说明 a[i] 是第一次出现，写入 a[j] 并 j++。扫描结束后前 j 个元素互不相同，j 即新长度。
例题：区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l, r] 之间的所有数的和。
输入格式： 第一行包含两个整数 n 和 m。 接下来 n 行，每行包含两个整数 x 和 c。 再接下来 m 行，每行包含两个整数 l 和 r。
输出格式： 共 m 行，每行输出一个询问中所求的区间内数字和。
import java.util.*;
public class Main {
static ArrayList<Integer> alls = new ArrayList<>(); static ArrayList<Map.Entry<Integer,Integer>> add = new ArrayList<>(); static ArrayList<Map.Entry<Integer,Integer>> query = new ArrayList<>();
public static void main(String[] args) { Scanner sc= new Scanner(System.in); int n =sc.nextInt(); int m = sc.nextInt(); int[] a = new int[300010]; int[] s = new int[300010]; for (int i = 0; i < n; i++) { int x =sc.nextInt(); int c= sc.nextInt(); add.add(new AbstractMap.SimpleEntry<>(x,c)); alls.add(x); } for (int i = 0; i < m; i++) { int l = sc.nextInt(); int r = sc.nextInt(); query.add(new AbstractMap.SimpleEntry<>(l,r)); alls.add(l); alls.add(r); } Collections.sort(alls); int len = unique(alls); List<Integer> newList = alls.subList(0,len + 1); for (Map.Entry<Integer, Integer> integerIntegerEntry : add) { int x = find(integerIntegerEntry.getKey()); a[x] += integerIntegerEntry.getValue(); } //预处理前缀和 for (int i = 1; i <= newList.size(); i++) { s[i] = s[i-1] + a[i]; } //处理询问 for (Map.Entry<Integer, Integer> integerIntegerEntry : query) { int l = find(integerIntegerEntry.getKey()); int r = find(integerIntegerEntry.getValue()); System.out.println(s[r] - s[l -1]); } } public static int find(int x){ int l = 0; int r = alls.size()-1; while (l < r ){ int mid = (l+r)>> 1; if(alls.get(mid) >= x){ r = mid; }else{ l = mid + 1; } } return r + 1; } public static int unique(ArrayList<Integer> arrayList){ int j = 0; for (int i = 0; i < arrayList.size(); i++) { if(i == 0 || arrayList.get(i) != arrayList.get(i-1)){ arrayList.set(j++,arrayList.get(i)); } } return j; }}代码流程梳理： 先把所有”加点坐标 x”和”询问端点 l、r”收集进 alls；排序去重后，用二分 find(x) 把每个坐标映射成从 1 开始的紧凑下标；在紧凑数组上做加点、前缀和；最后每个询问同样通过 find 映射后用前缀和 O(1) 求区间和。总复杂度 O((n + m) log(n + m))，与坐标值域大小无关。
区间合并
区间合并就是将多个区间中存在交集的区间合并为一个区间
1.按区间左端点排序
2.扫描整个区间，把所有可能合并的区间合并
算法思路： 把所有区间按左端点从小到大排序；维护一个”当前正在合并的区间” [st, ed]（初始设为一个不可能出现的值，如 st = ed = -2e9）。扫描每个区间 [l, r]，分两种情况：
- l > ed： 新区间与当前区间没有交集，把当前区间 [st, ed] 存入答案，然后把 [l, r] 作为新的当前区间；
- l ≤ ed： 有交集（注意端点相交也算交集），只需把右端点扩大为
ed = max(ed, r)。
扫描结束后别忘了把最后一个区间也存入答案。答案列表的大小就是合并后的区间个数。
给定 n 个区间 [l, r]，要求合并所有有交集的区间。 注意：如果在端点处相交，也算有交集。 输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式：
- 第一行包含整数 n。
- 接下来 n 行，每行包含两个整数 l 和 r。
输出格式：
共一行，包含一个整数，表示合并区间完成后的区间个数。
import java.util.*;
public class Main { public static List<Map.Entry<Integer, Integer>> merge(List<Map.Entry<Integer,Integer>> segs){ segs.sort(Map.Entry.<Integer,Integer>comparingByKey().thenComparing(Map.Entry.comparingByValue())); List<Map.Entry<Integer,Integer>> res = new ArrayList<>(); int st = (int)-2e9; int ed = (int)-2e9; for (Map.Entry<Integer, Integer> seg : segs) { if(ed < seg.getKey()){ if(st != -2e9) res.add(new AbstractMap.SimpleEntry<>(st,ed)); st = seg.getKey(); ed = seg.getValue(); }else{ ed = Math.max(ed , seg.getValue()); }
} if(st != -2e9) res.add(new AbstractMap.SimpleEntry<>(st,ed)); for (Map.Entry<Integer, Integer> re : res) { System.out.println(re.getKey() + "---" + re.getValue()); } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); List<Map.Entry<Integer,Integer>> segs = new ArrayList<>(); int n = sc.nextInt(); for (int i = 0; i < n; i++) { int l = sc.nextInt(); int r= sc.nextInt(); segs.add(new AbstractMap.SimpleEntry(l,r)); } List<Map.Entry<Integer,Integer>> res = merge(segs); System.out.println(res.size()); }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时