网络信号最好的坐标
难度:
标签:
题目描述
给你一个数组 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 没有别的坐标有更大的信号强度。
示例 2：
输入：towers = [[23,11,21]], radius = 9 输出：[23,11] 解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。
示例 3：
输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2 输出：[1,2] 解释：坐标 (1, 2) 的信号强度最大。
提示：
1 <= towers.length <= 50towers[i].length == 30 <= xi, yi, qi <= 501 <= radius <= 50
代码结果
运行时间: 586 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Stream API遍历所有可能的坐标点 (x, y)，计算每个坐标点的信号强度。
* 对于每个坐标点，计算它与每个信号塔的距离，如果在有效范围内，则计算该塔在此点的信号强度。
* 累加所有能到达该点的塔的信号强度，记录信号强度最大的坐标点。
*/
import java.util.stream.IntStream;
public class Solution {
public int[] bestCoordinate(int[][] towers, int radius) {
int[] result = new int[2];
int[] maxSignal = {0};
IntStream.range(0, 51).forEach(x -> {
IntStream.range(0, 51).forEach(y -> {
int signal = IntStream.range(0, towers.length).map(i -> {
int distSq = (towers[i][0] - x) * (towers[i][0] - x) + (towers[i][1] - y) * (towers[i][1] - y);
if (distSq <= radius * radius) {
return (int)Math.floor(towers[i][2] / (1 + Math.sqrt(distSq)));
} else {
return 0;
}
}).sum();
if (signal > maxSignal[0] || (signal == maxSignal[0] && (x < result[0] || (x == result[0] && y < result[1])))) {
maxSignal[0] = signal;
result[0] = x;
result[1] = y;
}
});
});
return result;
}
}解释
方法:
该题解采用了暴力搜索法，考察所有可能的坐标点，并计算每个点的总信号强度。对于每个坐标点 (x, y)，我们遍历所有塔，计算每座塔对该点的信号贡献。如果塔与该点的距离小于等于radius，那么该塔的信号可以到达该坐标，并按照给定公式计算贡献。最后，选择总信号强度最大的坐标点，并在有多个坐标得分相同的情况下，选择字典序最小的坐标。
时间复杂度:
O(n * x_max * y_max)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择暴力搜索法来解决这个问题，而不是使用更高效的算法或数据结构？
▷🦆
在计算两点之间的距离时，为什么选择使用距离的平方进行比较，而不是直接计算欧几里得距离？
▷🦆
在对信号强度进行计算时，使用了整数除法 `int(q / (1 + dis**(1/2)))`，这种计算方式是否可能因为取整而导致精度损失？
▷🦆
如果有多个坐标点的信号强度相同，题解中提到选择字典序最小的坐标，具体是如何实现这一点的？
▷