seo整站优化外包服务,小型私人会所装修设计,书签制作简单漂亮图片,网站备案人授权书1. 题目
给定一个二维平面及平面上的 N 个点列表Points#xff0c;其中第i个点的坐标为Points[i][Xi,Yi]。 请找出一条直线#xff0c;其通过的点的数目最多。
设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S#xff0c;你仅需返回[S[0],S[1]]作为答案 若有多…1. 题目
给定一个二维平面及平面上的 N 个点列表Points其中第i个点的坐标为Points[i][Xi,Yi]。 请找出一条直线其通过的点的数目最多。
设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S你仅需返回[S[0],S[1]]作为答案 若有多条直线穿过了相同数量的点则选择S[0]值较小的直线返回S[0]相同则选择S[1]值较小的直线返回。
示例
输入 [[0,0],[1,1],[1,0],[2,0]]
输出 [0,2]
解释 所求直线穿过的3个点的编号为[0,2,3]提示
2 len(Points) 300
len(Points[i]) 2来源力扣LeetCode 链接https://leetcode-cn.com/problems/best-line-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
暴力法固定一个点遍历所有剩余的采用嵌套的哈希map第一层key存储斜率第二层key存储截距value为点的set集合存储下标斜率不存在单独再开一个哈希表key为与 x 轴的截距value为点集合遍历所有集合找最多的对相等长度的点集合排序取出题目要求的最小的下标的时间复杂度 O(n2)O(n^2)O(n2)
class Solution {
public:vectorint bestLine(vectorvectorint points) {int i, j, g, dx, dy, maxCount 0, n points.size();double k, b;unordered_mapdouble,unordered_mapdouble,setint m;//k,b,pointsunordered_mapdouble,setint v;//x轴截距斜率不存在时的集合vectorsetint ans;for(i 0; i n-1; i){for(j i1; j n; j){dx points[j][0]-points[i][0];dy points[j][1]-points[i][1];if(dx0)//斜率不存在{if(v[double(points[i][0])].empty())v[double(points[i][0])].insert(i);v[double(points[i][0])].insert(j);}else{k double(dy)/dx;b double(points[i][1])-points[i][0]*k;if(m[k][b].empty())m[k][b].insert(i);m[k][b].insert(j);}}}for(auto mi : m){for(auto mii : mi.second){if(mii.second.size() maxCount){maxCount mii.second.size();ans.clear();ans.push_back(mii.second);}else if(mii.second.size() maxCount)ans.push_back(mii.second);}}for(auto vi : v){if(vi.second.size() maxCount){maxCount vi.second.size();ans.clear();ans.push_back(vi.second);}else if(vi.second.size() maxCount)ans.push_back(vi.second);}sort(ans.begin(),ans.end(),[](auto a, auto b){auto it1 a.begin(), it2 b.begin();if(*it1 *it2)return *(it1) *(it2);return *it1 *it2;});auto it ans[0].begin();return {*it,*(it)};}
};660 ms 117.7 MB
