邻值查找

题目 邻值查找

思路分析

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)。

代码实现

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();

    }

}

同类题型

视频讲解

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