力扣(LeetCode)1620. 网络信号最好的坐标(C++)

一、环境说明

1. 本文是 LeetCode1620. 网络信号最好的坐标。
2. 暴力。
3. 测试环境:Visual Studio 2019。

二、思路分析

三重循环

提示:所有塔都是正坐标，那么信号最好的点一定是正坐标，不用考虑负坐标。

遍历 { x ( 0 , 50 ) , y ( 0 , 50 ) } \{x(0,50),y(0,50)\} {x(0,50),y(0,50)}的点，$2601$个点。和$autop:towers$比较。$2601\times 50=130050$。问题规模合适。

• 距离 $d=\sqrt{(p[0]-x)\times (p[0]-x)+(p[1]-y)\times (p[1]-y)}$
• 信号 $q=p[2]÷(1+\sqrt{d})$。

暴力循环天然按照字典序遍历，所以只要保存第一次出现的$max$的坐标，即为所求。

三、代码展示

class Solution {
public:
    vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
        int max = 0;//最大信号
        vector<int> ans={0,0};
        for(int x = 0;x<=50;x++)
            for(int y = 0;y<=50;y++){
                int q=0;//q当前信号
                for(auto p:towers){//遍历每个towers
                    double d = sqrt((p[0]-x)*(p[0]-x)+(p[1]-y)*(p[1]-y));
                    if(d<=radius) q += p[2] / (1 + d);
                }
                if(max<q){
                    max = q;
                    ans = {x,y};
                }
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(x\times y\times n)$ ,$n$是$towers$的总数,$x$是塔的$x$坐标范围，$y$是塔的$y$坐标范围。三重循环的时间复杂度是$O(x\times y\times n)$。
2. 空间复杂度:$O(1)$,只使用到了常量级空间，没有使用额外的线性空间。