1779. 找到最近的有相同 X 或 Y 坐标的点

小目标：百篇题解之四，破百开源成库。关注我（Github、力扣），即可获取最新题解。
微信二维码

题目描述

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 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 <= 104
  • points[i].length == 2
  • 1 <= x, y, ai, bi <= 104

相关信息：

  • 难度：简单
  • 标签：数组

题解

本题题意相对简单，主要需要处理的要求有三个：

  1. 判断点是否有效；
  2. 计算曼哈顿距离并判断大小
  3. 曼哈顿距离相同时，取下标最小值

前面两个条件是很好处理的，只是其中第三个条件值得考虑是否需要单独处理？我认为在满足特定情况下，并不一定需要单独处理，比如在循环时，保证从头到尾以此进行，那index也是从小到大有序的，此时不必单独处理。

通过查看本题题解发现，目前本题普遍的解法都是循环，只是在判断上诉三个条件时的处理方式不一样。

方法一：for 循环

/*
执行用时: 140 ms
内存消耗: 45.6 MB
*/
var nearestValidPoint = function(x, y, points) {
    let minIndex=-1;//最小下标
    let minAbs=Infinity;//最小曼哈顿距离
    for(let i=0;i<points.length;i++){
        if(points[i][0]===x||points[i][1]===y){
            let abs=Math.abs(points[i][0]-x)+Math.abs(points[i][1]-y);
            //计算曼哈顿距离
            if(abs<minAbs){
              //这里不必再单独处理曼哈顿距离相同时的情况了
                minAbs=abs;
                minIndex=i;
            }
        }
    };
    return minIndex;
};

方法二：使用 Array.reduce()

/*
执行用时: 152 ms
内存消耗: 45.1 MB
*/
var nearestValidPoint = function(x, y, points) {
    let out = points.reduce((pre,val,index)=>{
        if(val[0]==x||val[1]==y){
            //判断是否为有效点
            let abs=Math.abs(x-val[0])+Math.abs(y-val[1]);
            //计算曼哈顿距离
            if(abs<pre[1]){
                //此处不必再单独考虑距离相同时取下标较小值的问题，因为reduce遍历数组是从头向尾遍历的
                pre=[index,abs]
            }  
        }
        return pre;//不管pre有没有修改，都得将最后的结果返回回去，以便进行下一轮时pre有值。
    },[-1,Infinity])
    return out[0];
};

方法三：分开判断两种有效点

/*
执行用时: 136 ms
内存消耗: 45.7 MB
*/
var nearestValidPoint = function(x, y, points) {
    let out = points.reduce((pre,val,index)=>{
        //将两种最小曼哈顿距离的有效点分开计算
        if(val[0]===x&&Math.abs(val[1]-y)<pre[1]){
            pre=[index,Math.abs(val[1]-y)] 
        }
        if(val[1]===y&&Math.abs(val[0]-x)<pre[1]){
             pre=[index,Math.abs(val[0]-x)]
        }
        return pre;
    },[-1,Infinity])
    return out[0];
};

以上就是本题的所有题解啦，感谢你能看到这里，如果本文对你有所帮助的话，别忘了给一个点赞三连嗷～当然如果你对题解中的代码有不一样的优化意见，也欢迎你在评论区指出～