---
title: "05-邻值查找"
created: 2025-12-02
tags:
  - 项目
aliases:
  - 邻值查找
---
# 邻值查找

## 题目 [邻值查找](https://www.acwing.com/problem/content/138/)

![[image-14f6a41f.png]]

## 思路分析

1. **读取输入**：使用 `BufferedReader` 高效地读取输入数据，分别读取数组的长度 `n` 和数组 `w` 的元素。
2. **使用** `TreeMap`：利用 `TreeMap` 的有序特性，快速找到与当前元素最接近的元素。`TreeMap` 的键表示数组元素的值，值表示该元素的索引。
3. **寻找最近元素**：对于每个元素 `w[i]`，查找 `TreeMap` 中大于或等于 `w[i]` 的最小键 `up` 和小于或等于 `w[i]` 的最大键 `down`。
   - 比较 `w[i]` 与 `up` 和 `down` 的差值，找到差值最小的元素。
   - 如果差值相同，返回位置较小的那个元素。
4. **更新** `TreeMap`：将每个处理过的元素存储到 `TreeMap` 中，以便在后续步骤中使用。
5. **输出结果**：使用 `BufferedWriter` 高效输出结果。

- **时间复杂度**：每次查找和插入操作的时间复杂度为 O(log N)，总的时间复杂度为 O(N log N)，其中
  N 是数组的长度。
- **空间复杂度**：使用了一个 `TreeMap` 来存储处理过的元素，因此空间复杂度为 O(N)。

## 代码实现

```java
import java.util.*;

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {

        // 使用 BufferedReader 读取输入和 BufferedWriter 输出结果，提供高效的 I/O

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        // 读取数组 w 的所有元素，并将其存储到字符串数组中

        String[] strs = br.readLine().split(" ");

        int[] w = new int[n];

        // 将字符串数组中的每个元素转换为整数并存储到整数数组 w 中

        for (int i = 0; i < n; i++)

            w[i] = Integer.parseInt(strs[i]);

        // 使用 TreeMap 来存储已经处理过的元素及其对应的索引

        TreeMap<Integer, Integer> map = new TreeMap<>();

        // 将第一个元素存入 TreeMap 中，值为 w[0]，索引为 0

        map.put(w[0], 0);

        // 从第二个元素开始，逐个处理每个元素

        for (int i = 1; i < n; i++) {

            // 查找 TreeMap 中大于或等于 w[i] 的最小键（向上取整的键值对）

            Map.Entry<Integer, Integer> up = map.ceilingEntry(w[i]);

            // 查找 TreeMap 中小于或等于 w[i] 的最大键（向下取整的键值对）

            Map.Entry<Integer, Integer> down = map.floorEntry(w[i]);

            // 初始化 res 和 pos，分别表示最小距离和对应的索引

            int res = Integer.MAX_VALUE, pos = -1;

            // 如果 down 存在，计算 w[i] 与 down 的差值

            if (down != null) {

                res = w[i] - down.getKey(); // 计算距离

                pos = down.getValue(); // 记录索引

            }

            // 如果 up 存在，且与 w[i] 的差值比当前的 res 更小，则更新 res 和 pos

            if (up != null && up.getKey() - w[i] < res) {

                res = up.getKey() - w[i];

                pos = up.getValue();

            }

            // 输出当前元素 w[i] 与最接近的元素之间的差值和最接近元素的位置（索引加 1）

            bw.write(res + " " + (pos + 1) + "\n");

            // 将当前元素 w[i] 及其索引 i 存入 TreeMap 中

            map.put(w[i], i);

        }

        // 刷新输出流，确保所有结果都被输出

        bw.flush();

    }

}
```

## 同类题型

## 视频讲解

---

**项目分区导航**： [[04-模拟队列|模拟队列]] ⬅️ | 05-邻值查找 |  ➡️ [[00-类与接口|类与接口]]