1779. 找到最近的有相同 X 或 Y 坐标的点
1779. 找到最近的有相同 X 或 Y 坐标的点
题目
You are given two integers, x
and y
, which represent your current location on a Cartesian grid: (x, y)
. You are also given an array points
where each points[i] = [ai, bi]
represents that a point exists at (ai, bi)
. A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.
Return the index**(0-indexed)** of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with thesmallest index. If there are no valid points, return -1
.
The Manhattan distance between two points (x1, y1)
and (x2, y2)
is abs(x1 - x2) + abs(y1 - y2)
.
Example 1:
Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.
Example 2:
Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.
Example 3:
Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.
Constraints:
1 <= points.length <= 10^4
points[i].length == 2
1 <= x, y, ai, bi <= 10^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
解题思路
遍历所有点:
- 使用
for
循环依次检查每个点[nx, ny]
是否是有效点。 - 有效点定义为
nx == x
或ny == y
。
- 使用
计算曼哈顿距离:
- 对于每个有效点,计算其到给定坐标
(x, y)
的曼哈顿距离:distance = |nx - x| + |ny - y|
- 对于每个有效点,计算其到给定坐标
更新最近距离:
- 使用变量
minDistance
跟踪最小的曼哈顿距离,初始值设为Infinity
。 - 如果当前点的距离比
minDistance
小,则更新minDistance
和记录其索引。
- 使用变量
返回结果:
- 遍历完成后,如果没有有效点,则返回
-1
。 - 否则,返回拥有最小曼哈顿距离的点的索引。
- 遍历完成后,如果没有有效点,则返回
复杂度分析
- 时间复杂度:
O(n)
,其中n
是点的数量,遍历points
一次。 - 空间复杂度:
O(1)
,仅使用了常量空间。
代码
/**
* @param {number} x
* @param {number} y
* @param {number[][]} points
* @return {number}
*/
var nearestValidPoint = function (x, y, points) {
let minDistance = Infinity,
idx = -1;
for (let i = 0; i < points.length; i++) {
const [nx, ny] = points[i];
let dis;
if (nx == x) {
dis = Math.abs(ny - y);
} else if (ny == y) {
dis = Math.abs(nx - x);
} else {
continue;
}
if (dis < minDistance) {
minDistance = dis;
idx = i;
}
}
return idx;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
973 | 最接近原点的 K 个点 | [✓] | 几何 数组 数学 4+ | 🟠 | 🀄️ 🔗 |