给定一个二维平面及平面上的 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<int> bestLine(vector<vector<int>>& points) {
int i, j, g, dx, dy, maxCount = 0, n = points.size();
double k, b;
unordered_map<double,unordered_map<double,set<int>>> m;//k,b,points
unordered_map<double,set<int>> v;//x轴截距,斜率不存在时的集合
vector<set<int>> ans;
for(i = 0; i < n-1; ++i)
{
for(j = i+1; j < n; ++j)
{
dx = points[j][0]-points[i][0];
dy = points[j][1]-points[i][1];
if(dx==0)//斜率不存在
{
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