跳至主要內容

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


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

🟢   🔖  数组  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你两个整数 xy ,表示你在一个笛卡尔坐标系下的 (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

解题思路

  1. 遍历所有点

    • 使用 for 循环依次检查每个点 [nx, ny] 是否是有效点。
    • 有效点定义为 nx == xny == y
  2. 计算曼哈顿距离

    • 对于每个有效点,计算其到给定坐标 (x, y) 的曼哈顿距离: distance = |nx - x| + |ny - y|
  3. 更新最近距离

    • 使用变量 minDistance 跟踪最小的曼哈顿距离,初始值设为 Infinity
    • 如果当前点的距离比 minDistance 小,则更新 minDistance 和记录其索引。
  4. 返回结果

    • 遍历完成后,如果没有有效点,则返回 -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+🟠🀄️open in new window 🔗open in new window