跳转至

4024. 最近的可用无人机

题目描述

给你一个二维整数数组 drones，其中 drones[i] = [xi, yi, rangei] 表示第 ith 架无人机的横坐标、纵坐标和飞行范围。

另给你一个整数数组 target = [tx, ty]，表示目标的坐标。

如果无人机 drones[i] 的坐标与目标坐标之间的曼哈顿距离小于或等于其 rangei，则该无人机能够到达目标。

返回能够到达目标且与目标之间曼哈顿距离最小的无人机的下标。如果存在多个符合条件的无人机，则返回其中最小的下标。如果没有无人机能够到达目标，则返回 -1。

两个坐标 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

 

示例 1：

输入： drones = [[0,0,8],[2,2,9]], target = [3,4]

输出： 1

解释：

  • drones[0] 与 target 之间的距离为 |0 - 3| + |0 - 4| = 7，没有超出其飞行范围 8。
  • drones[1] 与 target 之间的距离为 |2 - 3| + |2 - 4| = 3，没有超出其飞行范围 9。
  • 由于 drones[1] 是距离目标最近的无人机，因此答案为 1。

示例 2：

输入： drones = [[2,1,5],[4,4,5],[6,6,8]], target = [5,5]

输出： 1

解释：

  • drones[0] 与 target 之间的距离为 |2 - 5| + |1 - 5| = 7，大于其飞行范围 5。
  • drones[1] 与 target 之间的距离为 |4 - 5| + |4 - 5| = 2，没有超出其飞行范围 5。
  • drones[2] 与 target 之间的距离为 |6 - 5| + |6 - 5| = 2，没有超出其飞行范围 8。
  • drones[1] 和 drones[2] 都是距离目标最近的无人机。由于需要返回最小下标，因此答案为 1。

示例 3：

输入： drones = [[4,4,5]], target = [8,6]

输出： -1

解释：

  • drones[0] 与 target 之间的距离为 |4 - 8| + |4 - 6| = 6，大于其飞行范围 5。
  • 没有无人机能够到达目标，因此答案为 -1。

 

提示：

  • 1 <= drones.length <= 100
  • drones[i] = [xi, yi, rangei]
  • target = [tx, ty]
  • -25 <= xi, yi, tx, ty <= 25
  • 1 <= rangei <= 100

解法

方法一：遍历

我们遍历每一架无人机，计算其与目标的曼哈顿距离 \(d = |x_i - t_x| + |y_i - t_y|\)。若 \(d \le \textit{range}_i\)，则该无人机可达。在所有可达无人机中，选择距离最小的一架；若距离相同，由于我们从左到右遍历且仅在距离严格更小时更新答案，因此会自动保留更小的下标。若没有可达无人机，返回 \(-1\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是无人机的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def nearestDrone(self, drones: list[list[int]], target: list[int]) -> int:
        ans = -1
        mn = inf
        tx, ty = target
        for i, (x, y, r) in enumerate(drones):
            d = abs(x - tx) + abs(y - ty)
            if d <= r and mn > d:
                ans = i
                mn = d
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int nearestDrone(int[][] drones, int[] target) {
        int ans = -1;
        int mn = Integer.MAX_VALUE;
        int tx = target[0], ty = target[1];

        for (int i = 0; i < drones.length; i++) {
            int x = drones[i][0];
            int y = drones[i][1];
            int r = drones[i][2];

            int d = Math.abs(x - tx) + Math.abs(y - ty);

            if (d <= r && mn > d) {
                ans = i;
                mn = d;
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int nearestDrone(vector<vector<int>>& drones, vector<int>& target) {
        int ans = -1;
        int mn = INT_MAX;
        int tx = target[0], ty = target[1];

        for (int i = 0; i < drones.size(); i++) {
            int x = drones[i][0];
            int y = drones[i][1];
            int r = drones[i][2];

            int d = abs(x - tx) + abs(y - ty);

            if (d <= r && mn > d) {
                ans = i;
                mn = d;
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func nearestDrone(drones [][]int, target []int) int {
    ans := -1
    mn := math.MaxInt32
    tx, ty := target[0], target[1]

    for i, drone := range drones {
        x, y, r := drone[0], drone[1], drone[2]

        d := abs(x-tx) + abs(y-ty)

        if d <= r && mn > d {
            ans = i
            mn = d
        }
    }

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function nearestDrone(drones: number[][], target: number[]): number {
    let ans = -1;
    let mn = Infinity;
    const [tx, ty] = target;

    for (let i = 0; i < drones.length; i++) {
        const [x, y, r] = drones[i];

        const d = Math.abs(x - tx) + Math.abs(y - ty);

        if (d <= r && mn > d) {
            ans = i;
            mn = d;
        }
    }

    return ans;
}

评论