我正在解决一个问题,我的问题是在某个测试中出现TL(时间限制)错误(代码在条件之后呈现),我不知道如何加速算法以便测试通过,也许我的逻辑有问题——我无法否认这一点。
问题条件:给定两个数组a和b,长度为N,由整数组成。考虑一个由连接点 (0, ai) 和 (1, bi) 的线段组成的集合,其中 1 <= i <= N。找出该集合中不与其他线段相交的线段的数量。
相交是指至少有一个公共点的线段,即具有相同端点的线段相交。
输入格式
在第一行中输入 N (1 <= N <= 3 * 10^5) - 段数。接下来,N 行包含由空格 ai 和 bi 分隔的 2 个整数(1 <= ai, bi <= 2 * N),指定第 i 段的坐标。保证输入中指定的所有段都不同,即对于 i != j,至少满足条件 ai != aj 和 bi != bj 之一
代码:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Map<Integer, ArrayList<Integer>> nums = new HashMap<>();
int amount = sc.nextInt();
sc.nextLine();
for (int i = 0; i < amount; i++) {
String[] point = sc.nextLine().split(" ");
int x = Integer.parseInt(point[0]);
int y = Integer.parseInt(point[1]);
if (!nums.containsKey(x)) {
nums.put(x, new ArrayList<>());
}
nums.get(x).add(y);
}
int count = 0;
for (int key1 : nums.keySet()) {
boolean intersects = false;
ArrayList<Integer> values1 = nums.get(key1);
for (int key2 : nums.keySet()) {
if (key1 != key2) {
ArrayList<Integer> values2 = nums.get(key2);
for (int value1 : values1) {
for (int value2 : values2) {
if ((key1 < key2 && value1 >= value2) || (key1 > key2 && value2 >= value1)) {
intersects = true;
break;
}
}
if (intersects) {
break;
}
}
if (intersects) {
break;
}
}
}
if (!intersects) {
count++;
}
}
System.out.println(count);
}
}
你不必将所有事情都进行比较。
看看你的照片
假设您沿着坐标 (0,ai) 从左向右移动,您会发现如果 a0=1 且 b0=4,则 ai >= a0 且 bi<=b0 的任何其他线段都将与第一条线段相交。
由于我们是从左到右,这意味着在处理下一对ai、bi时,为了了解这对是否与另一对相交,我们只需要知道之前所有值中的最大值aMax和bMax即可。如果 ai == aMax - 那么这些线段与前面的线段在点 ai 处相交。如果 bi <= bmax - 则线段 bi 与已处理的某个线段相交。
这样,我们就得到了一个线性算法(除了 NlogN 排序之外)。C# 中的一个示例,我首先从左到右,然后从右到左。
考试
结论
令a i为线段的下端,构造索引i k使得序列a i k不减少。
类似地,索引j k使得序列b j k不减。
对于一个线段 ( a m , b m ) 来说,它是孤独的,所有其他线段必须完全位于它的左侧或右侧。设它的左边有k 个线段,其余的都在右边。则i k = m - k个线段下端中单个线段下端的左侧。类似地,j k = m - k 个线段上端中单个线段上端的左侧。m的具体值并不重要。重要的是所有孤独段都有i k = j k。
孤独线段的相邻线段的下端与它不重合:a i k-1 < a i k < a i k+1。同样,上端也不重合: b j k-1 < b j k < b j k+1。
我们迭代k。在孤独片段之前开始的所有片段都必须在它之前结束。为此,我们根据段数创建一个标志数组。当段开始或结束时,相应的标志被反转。在孤独段之前,必须重置所有标志。
下面的程序体现了这三个想法。运行时间为O(nlogn)。