leetcode
leetcode 2351 ~ 2400
找到最近的标记节点

找到最近的标记节点

难度:

标签:

题目描述

代码结果

运行时间: 49 ms, 内存: 17.9 MB


/*
题目思路:
1. 输入为一个整数数组和一个目标值。
2. 我们需要找到数组中距离目标值最近的元素。
3. 返回该元素的索引。
4. 使用Java Stream API简化实现。
*/

import java.util.stream.IntStream;

public class FindClosestNodeStream {
    public int findClosest(int[] nums, int target) {
        return IntStream.range(0, nums.length)
                .boxed()
                .min((i, j) -> Integer.compare(Math.abs(nums[i] - target), Math.abs(nums[j] - target)))
                .orElse(-1);
    }

    public static void main(String[] args) {
        FindClosestNodeStream solution = new FindClosestNodeStream();
        int[] nums = {1, 3, 7, 8, 9};
        int target = 5;
        System.out.println(solution.findClosest(nums, target)); // Output: 1
    }
}

解释

方法:

该题解采用了带优先级队列的Dijkstra算法来寻找从起点s到任意标记节点的最短距离。首先,将所有标记节点存储在集合中以便快速检查。接着,构建图的邻接表表示,然后使用一个优先队列(最小堆)来维护当前节点到起点的距离。每次从队列中取出距离最小的节点,如果该节点是标记节点,则直接返回其距离。否则,更新其邻接节点的距离,并将更新后的距离和节点推入队列中。如果遍历完所有可达节点后未找到标记节点,则返回-1。

时间复杂度:

O((V + E) log V)

空间复杂度:

O(V + E)

代码细节讲解

🦆
在Dijkstra算法中,使用优先队列(最小堆)的目的是什么?为什么这种数据结构适合于此算法?
Dijkstra算法的核心目的是从起点出发逐步扩展路径,直至找到目标节点的最短路径。在这个过程中,优先队列(最小堆)被用来高效地获取当前未处理节点中距离起点最近的节点。这是因为优先队列能够保证每次从中取出的都是具有最小距离的节点,这样可以确保算法按照从近到远的顺序处理节点,有效地实现贪心策略。使用其他数据结构如数组或链表虽然也可以实现类似功能,但需要线性时间来查找最小元素,而优先队列的插入和删除操作通常是对数时间复杂度,因此更适合实现Dijkstra算法。
🦆
题解中提到,如果当前节点已经不是最优距离就跳过,这种策略是如何确保算法的效率的?它会不会导致某些节点的距离没有得到正确更新?
在Dijkstra算法实现中,如果一个节点的当前处理距离大于已记录的最短距离,说明该距离已被更新过且存在更优的路径。因此跳过这样的节点可以避免重复处理和不必要的计算,进而提高算法效率。这种策略不会导致节点距离更新错误,因为一旦节点的最短距离被确定并记录,后续出现的更长的距离不会对结果产生影响。这是因为Dijkstra算法的贪心性质保证了一旦找到最短路径,就不会有更短的路径出现于后续的操作中。
🦆
当所有标记节点都不可达时,题解选择返回-1。这种设计对算法的应用场景有什么影响?是否有其他可能的返回值设计?
在题解中返回-1作为标记节点不可达的信号是一种常见的做法,这帮助调用者区分找到有效路径与无法到达任何标记节点的场景。这种设计简洁明了,适用于多数情况,特别是在需要明确区分处理结果的情况下。然而,其他可能的设计包括返回一个更详细的错误码、异常处理或是返回一个包含状态信息的复杂对象(如路径长度和状态描述),这些都可以根据具体应用需求和上下文环境来决定。
🦆
为什么需要将标记节点转换为集合来进行快速查找?直接在列表中查找有什么潜在的性能问题?
将标记节点转换为集合可以大幅提高查找效率。在集合中,查找操作通常是平均时间复杂度为O(1)的,这是因为集合内部通过哈希表实现。相比之下,在列表中查找一个元素的时间复杂度为O(n),因为可能需要遍历整个列表来找到一个元素或确认元素不存在。特别是在标记节点数量较多或查找操作频繁的情况下,使用集合可以显著降低算法的总体时间复杂度。

相关问题