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

Kim Yang 4/15/2021 LeetCodeAlgorithm

# 1779. 找到最近的有相同 X 或 Y 坐标的点 (opens new window)

# 题目描述

给你两个整数 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

相关信息：

难度：简单
标签：数组

# 题解

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

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

前面两个条件是很好处理的，只是其中第三个条件值得考虑是否需要单独处理？我认为在满足特定情况下，并不一定需要单独处理，比如在循环时，保证从头到尾以此进行，那 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];
};

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

# 全部代码

/*
 * @lc app=leetcode.cn id=1779 lang=javascript
 *
 * [1779] 找到最近的有相同 X 或 Y 坐标的点
 *
 * https://leetcode-cn.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/description/
 *
 * algorithms
 * Easy (64.69%)
 * Likes:    10
 * Dislikes: 0
 * Total Accepted:    5.1K
 * Total Submissions: 7.9K
 * Testcase Example:  '3\n4\n[[1,2],[3,1],[2,4],[2,3],[4,4]]'
 *
 * 给你两个整数 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 <= 10^4
 * points[i].length == 2
 * 1 <= x, y, ai, bi <= 10^4
 * 
 * 
 */

// @lc code=start
/**
 * @param {number} x
 * @param {number} y
 * @param {number[][]} points
 * @return {number}
 */
 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;
};
// @lc code=end

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];
};

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];
};

「690. 员工的重要性」题解「1832. 判断句子是否为全字母句」题解

Kim's Blog

Choose mode