Easy

题目描述

给你两个整数 x 和 y，表示你在一个笛卡尔坐标系中的位置 (x, y)。同时给你一个数组 points，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处存在一个点。当一个点与你所在的位置 (x, y) 拥有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是有效的。

请返回距离你当前位置曼哈顿距离最近的有效点的下标（下标从 0 开始）。如果存在多个，返回下标最小的一个。如果没有有效点，返回 -1。

两个点 (x1, y1) 和 (x2, y2) 之间的曼哈顿距离是 abs(x1 - x2) + abs(y1 - y2)。

示例 1：

输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
输出：2
解释：所有的点中，[3,1]，[2,4] 和 [4,4] 是有效的。在有效的点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1。[2,4] 的下标最小，所以返回 2。

示例 2：

输入：x = 3, y = 4, points = [[3,4]]
输出：0
解释：答案可以与你当前位置相同。

示例 3：

输入：x = 3, y = 4, points = [[2,3]]
输出：-1
解释：没有有效的点。

提示：

  • 1 <= points.length <= 10^4
  • points[i].length == 2
  • 1 <= x, y, ai, bi <= 10^4

解题思路

这是一道简单的遍历题，核心思路如下：

  1. 理解有效点条件：一个点是有效的当且仅当它与当前位置有相同的 x 坐标或相同的 y 坐标。

  2. 曼哈顿距离计算：对于有效点 (ai, bi)，其到当前位置 (x, y) 的曼哈顿距离为 abs(x - ai) + abs(y - bi)。

  3. 遍历策略：遍历所有点，对于每个点：

    • 首先检查是否为有效点（ai == x 或 bi == y）
    • 如果是有效点，计算曼哈顿距离
    • 维护最小距离和对应的最小下标

  4. 更新条件：当找到更小的距离时更新结果；当距离相同但下标更小时也需要更新（实际上由于我们从前往后遍历，这种情况不会发生）。

  5. 边界情况：如果没有找到任何有效点，返回 -1。

时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 是点的数量。

代码实现

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int minDistance = INT_MAX;
        int result = -1;
        
        for (int i = 0; i < points.size(); i++) {
            int px = points[i][0], py = points[i][1];
            
            // 检查是否为有效点
            if (px == x || py == y) {
                int distance = abs(x - px) + abs(y - py);
                
                // 更新最近的有效点
                if (distance < minDistance) {
                    minDistance = distance;
                    result = i;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        min_distance = float('inf')
        result = -1
        
        for i, (px, py) in enumerate(points):
            # 检查是否为有效点
            if px == x or py == y:
                distance = abs(x - px) + abs(y - py)
                
                # 更新最近的有效点
                if distance < min_distance:
                    min_distance = distance
                    result = i
        
        return result

public class Solution {
    public int NearestValidPoint(int x, int y, int[][] points) {
        int minDistance = int.MaxValue;
        int result = -1;
        
        for (int i = 0; i < points.Length; i++) {
            int px = points[i][0], py = points[i][1];
            
            // 检查是否为有效点
            if (px == x || py == y) {
                int distance = Math.Abs(x - px) + Math.Abs(y - py);
                
                // 更新最近的有效点
                if (distance < minDistance) {
                    minDistance = distance;
                    result = i;
                }
            }
        }
        
        return result;
    }
}

var nearestValidPoint = function(x, y, points) {
    let minDistance = Infinity;
    let result = -1;
    
    for (let i = 0; i < points.length; i++) {
        const [px, py] = points[i];
        
        if (px === x || py === y) {
            const distance = Math.abs(x - px) + Math.abs(y - py);
            
            if (distance < minDistance) {
                minDistance = distance;
                result = i;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有 n 个点，每个点的处理时间为常数
空间复杂度O(1)只使用了常数额外空间来存储变量

相关题目