136. 邻值查找
给定一个长度为 nn 的序列 AA,AA 中的数各不相同。
对于 AA 中的每一个数 AiAi,求:
min1≤j<i|Ai−Aj|min1≤j<i|Ai−Aj|
以及令上式取到最小值的 jj(记为 PiPi)。若最小值点不唯一,则选择使 AjAj 较小的那个。
输入格式
第一行输入整数 nn,代表序列长度。
第二行输入 nn 个整数A1…AnA1…An,代表序列的具体数值,数值之间用空格隔开。
输出格式
输出共 n−1n−1 行,每行输出两个整数,数值之间用空格隔开。
分别表示当 ii 取 2∼n2∼n 时,对应的 min1≤j<i|Ai−Aj|min1≤j<i|Ai−Aj| 和 PiPi 的值。
数据范围
n≤105n≤105,|Ai|≤109|Ai|≤109
输入样例:
3
1 5 3
输出样例:
4 1
2 1
题解:
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args)throws Exception {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long a[] = new long[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextLong();
}
TreeMap<Long, Integer> TreeMap = new TreeMap<>();
for (int i = 0; i < n; i++) {
if (i > 0) {
//获取到long最大值
long minn = Long.MAX_VALUE;
//pos为下标
int pos = -1;
//找到最小大于a[i]的数
Map.Entry<Long,Integer> upper = TreeMap.ceilingEntry(a[i]);
//找到最大小于a[i]的数
Map.Entry<Long,Integer> lower = TreeMap.floorEntry(a[i]);
//需要先判断最大小于a[i]的数
if (lower != null && Math.abs(lower.getKey() - a[i]) < minn){
minn = Math.abs(lower.getKey() - a[i]);
pos = lower.getValue();
}
if (upper != null && Math.abs(upper.getKey() - a[i]) < minn){
minn = Math.abs(upper.getKey() - a[i]);
pos = upper.getValue();
}
System.out.println(minn +" "+(pos+1));
}
//判断Map中是否存在当前值,不存在则添加进去
if (!TreeMap.containsKey(a[i])) TreeMap.put(a[i], i);
}
}
}
评论区