Medium

题目描述

给你一个网络基站数组 towers，其中 towers[i] = [xi, yi, qi] 表示第 i 个基站的位置为 (xi, yi) 且质量因子为 qi。所有坐标都是 X-Y 平面上的整数坐标，两个坐标之间的距离是欧几里得距离。

还给你一个整数 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 / (1 + sqrt(0))⌋ = ⌊7⌋ = 7
- 来自 (1, 2) 的质量为 ⌊5 / (1 + sqrt(2))⌋ = ⌊2.07⌋ = 2
- 来自 (3, 1) 的质量为 ⌊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 <= 50
  • towers[i].length == 3
  • 0 <= xi, yi, qi <= 50
  • 1 <= radius <= 50

解题思路

这是一道暴力枚举问题。由于约束条件很小（坐标范围 0-50，基站数量最多 50），我们可以枚举所有可能的整数坐标点，计算每个点的网络质量，找到最大值。

解题思路：

  1. 确定搜索范围：由于所有基站坐标都在 [0, 50] 范围内，而 radius 最大为 50，所以我们只需要检查 [0, 101] 范围内的坐标点即可覆盖所有可能的最优解。

  2. 计算网络质量：对于每个候选坐标 (x, y)，遍历所有基站：

    • 计算欧几里得距离：d = sqrt((x-xi)² + (y-yi)²)
    • 如果距离 ≤ radius，则该基站可达，计算信号质量：⌊qi / (1 + d)⌋
    • 累加所有可达基站的信号质量

  3. 找最优解：维护当前最大网络质量和对应坐标，遇到更大质量时更新，质量相等时选择字典序更小的坐标。

由于数据规模小，这种 O(n²×m) 的暴力解法完全可行，其中 n 是坐标范围，m 是基站数量。

优化细节：

  • 使用整数运算避免浮点误差
  • 提前判断距离是否超出半径，减少不必要的计算
  • 按字典序遍历坐标，简化最优解选择逻辑

代码实现

class Solution {
public:
    vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
        int maxQuality = 0;
        vector<int> result = {0, 0};
        
        // 枚举所有可能的坐标点
        for (int x = 0; x <= 100; x++) {
            for (int y = 0; y <= 100; y++) {
                int totalQuality = 0;
                
                // 计算当前坐标的网络质量
                for (auto& tower : towers) {
                    int tx = tower[0], ty = tower[1], tq = tower[2];
                    double distance = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));
                    
                    if (distance <= radius) {
                        totalQuality += (int)(tq / (1 + distance));
                    }
                }
                
                // 更新最优解（字典序遍历自动保证字典序最小）
                if (totalQuality > maxQuality) {
                    maxQuality = totalQuality;
                    result = {x, y};
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:
        max_quality = 0
        result = [0, 0]
        
        # 枚举所有可能的坐标点
        for x in range(101):
            for y in range(101):
                total_quality = 0
                
                # 计算当前坐标的网络质量
                for tx, ty, tq in towers:
                    distance = ((x - tx) ** 2 + (y - ty) ** 2) ** 0.5
                    
                    if distance <= radius:
                        total_quality += int(tq / (1 + distance))
                
                # 更新最优解（字典序遍历自动保证字典序最小）
                if total_quality > max_quality:
                    max_quality = total_quality
                    result = [x, y]
        
        return result

public class Solution {
    public int[] BestCoordinate(int[][] towers, int radius) {
        int maxQuality = 0;
        int[] result = {0, 0};
        
        // 枚举所有可能的坐标点
        for (int x = 0; x <= 100; x++) {
            for (int y = 0; y <= 100; y++) {
                int totalQuality = 0;
                
                // 计算当前坐标的网络质量
                foreach (var tower in towers) {
                    int tx = tower[0], ty = tower[1], tq = tower[2];
                    double distance = Math.Sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));
                    
                    if (distance <= radius) {
                        totalQuality += (int)(tq / (1 + distance));
                    }
                }
                
                // 更新最优解（字典序遍历自动保证字典序最小）
                if (totalQuality > maxQuality) {
                    maxQuality = totalQuality;
                    result = new int[] {x, y};
                }
            }
        }
        
        return result;
    }
}

var bestCoordinate = function(towers, radius) {
    let maxQuality = 0;
    let result = [0, 0];
    
    // 枚举所有可能的坐标点
    for (let x = 0; x <= 100; x++) {
        for (let y = 0; y <= 100; y++) {
            let totalQuality = 0;
            
            // 计算当前坐标的网络质量
            for (const [tx, ty, tq] of towers) {
                const distance = Math.sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));
                
                if (distance <= radius) {
                    totalQuality += Math.floor(tq / (1 + distance));
                }
            }
            
            // 更新最优解（字典序遍历自动保证字典序最小）
            if (totalQuality > maxQuality) {
                maxQuality = totalQuality;
                result = [x, y];
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(R² × N)
空间复杂度O(1)

其中 R 是坐标搜索范围（约 100），N 是基站数量（最多 50）。由于约束条件较小，该解法效率完全满足要求。