【1620. 网络信号最好的坐标】

来源：力扣（LeetCode）

描述：

给你一个数组 towers 和一个整数 radius 。

  数组 towers 中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi] 表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标都是在 X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。

  整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。

  如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。

  请你返回数组 [cx, cy] ，表示 信号强度 最大的 整数 坐标点 (cx, cy) 。如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。

注意：

• 坐标 (x1, y1) 字典序比另一个坐标 (x2, y2) 小，需满足以下条件之一：
  • 要么 x1 < x2 ，
  • 要么 x1 == x2 且 y1 < y2 。
• ⌊val⌋ 表示小于等于 val 的最大整数（向下取整函数）。

示例 1：

输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
输出：[2,1]
解释：
坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
1
2
3
4
5
6
7
8

示例 2：

输入：towers = [[23,11,21]], radius = 9
输出：[23,11]
解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。
1
2
3

示例 3：

输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
输出：[1,2]
解释：坐标 (1, 2) 的信号强度最大。
1
2
3

提示：

• 1 <= towers.length <= 50

• towers[i].length == 3

• 0 <= xi, yi, qi <= 50

• 1 <= radius <= 50

方法：枚举

  首先遍历所有的信号塔，获得所有信号塔的 x 坐标和 y 坐标的最大值，分别记为 Max 和 yMax。

在计算结果坐标 (cx, cy) 之前，首先考虑 cx 和 cy 的取值范围。

  假设坐标 (x1, y1) 满足 x1 > xMax 或 y1 > yMax，考虑坐标 (x2, y2)，其中 x2 = min(x1, xMax)，y2 = min(y1, yMax)，则对于任意一个信号塔，该信号塔到坐标 (x2, y2) 的距离一定小于等于到坐标 (x1, y1) 的距离。由于一个信号塔在一个坐标的信号强度随着距离的增加而减少或不变，因此坐标 (x1, y1) 处和坐标 (x2, y2) 处的网络信号相比，一定是坐标 (x2, y2) 处的网络信号更好或者两个坐标处的网络信号相同。由于题目要求返回字典序最小的网络信号最好的坐标，坐标 (x2, y2) 的字典序一定小于坐标 (x1, y1)，因此坐标 (x1, y1) 不可能是结果坐标。结果坐标一定满足 cx ≤ xMax 且 cy ≤ yMax。

  假设坐标 (x3, y3) 满足 x3 < 0 或 y3 < 0，考虑坐标 (x4, y4)，其中 x4 = max(x3, 0)，y4 = max(y3, 0)，则对于任意一个信号塔，由于信号塔的坐标非负，因此该信号塔到坐标 (x4, y4) 的距离一定小于等于到坐标 (x3, y3) 的距离。由于一个信号塔在一个坐标的信号强度随着距离的增加而减少或不变，因此坐标 (x3, y3) 处和坐标 (x4, y4) 处的网络信号相比，一定是坐标 (x4, y4) 处的网络信号更好或者两个坐标处的网络信号相同。

  根据题目要求，如果有多个网络信号最好的坐标，则返回网络信号最好的非负坐标，此时 cx ≥ 0 且 cy ≥ 0。如果只有一个网络信号最好的坐标，则根据上述分析可知，同样有 cx ≥ 0且 cy ≥ 0。

  因此结果坐标 (cx, cy) 满足 0 ≤ cx ≤ xMax 且 0≤ cy ≤ yMax，只需要在 0 ≤ cx ≤ xMax 且 0≤ cy ≤ yMax 的范围中遍历每一个坐标，计算该坐标处接收到的所有网络信号塔的信号强度之和，即该坐标的网络信号。遍历全部坐标之后，即可得到网络信号最好的坐标。

  为了确保结果坐标是字典序最小的网络信号最好的坐标，遍历时应分别将 x 和 y 从小到大遍历，只有当一个坐标的网络信号严格大于最好信号时才更新结果坐标。

  特别地，当一个网络信号塔与当前坐标的距离大于阈值 radius 时，该网络信号塔的信号不能到达当前信号，只有当距离不超过阈值 radius 时才计算信号强度。

代码：

class Solution {
public:
    vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
        int xMax = INT_MIN, yMax = INT_MIN;
        for (auto &&tower : towers) {
            int x = tower[0], y = tower[1];
            xMax = max(xMax, x);
            yMax = max(yMax, y);
        }
        int cx = 0, cy = 0;
        int maxQuality = 0;
        for (int x = 0; x <= xMax; x++) {
            for (int y = 0; y <= yMax; y++) {
                vector<int> coordinate = {x, y};
                int quality = 0;
                for (auto &&tower : towers) {
                    int squaredDistance = getSquaredDistance(coordinate, tower);
                    if (squaredDistance <= radius * radius) {
                        double distance = sqrt((double)squaredDistance);
                        quality += floor((double)tower[2] / (1 + distance));
                    }
                }
                if (quality > maxQuality) {
                    cx = x;
                    cy = y;
                    maxQuality = quality;
                }
            }
        }
        return {cx, cy};
    }

    int getSquaredDistance(const vector<int> &coordinate, const vector<int> &tower) {
        return (tower[0] - coordinate[0]) * (tower[0] - coordinate[0]) + (tower[1] - coordinate[1]) * (tower[1] - coordinate[1]);
    }
};
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
26
27
28
29
30
31
32
33
34
35
36

执行用时：108 ms, 在所有 C++ 提交中击败了30.95%的用户
内存消耗：17.4 MB, 在所有 C++ 提交中击败了13.09%的用户
复杂度分析
时间复杂度：O(R_x × R_y × n)，其中 R_x 和 R_y 分别是网络信号塔的 x 坐标和 y 坐标的最大值，n 是网络信号塔的数量。这道题中，每个网络信号塔的 x 坐标和 y 坐标的取值范围都是从 0 到 50，因此 R_x 和 R_y 都不超过 50。时间复杂度主要取决于遍历范围内的所有坐标。需要遍历 R_x × R_y个坐标，对于每个坐标，计算该坐标的网络信号需要遍历所有的网络信号塔，时间复杂度是 O(n)。因此时间复杂度是O(R_x × R_y × n)。
空间复杂度：O(1)。只需要使用常量的额外空间。
author：LeetCode-Solution