最佳直线
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/best-line-lcci/
题目描述
给定一个二维平面及平面上的 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) <= 300len(Points[i]) = 2
解法：
每个点两两计算斜率和截距，使用斜率和截距为键，把截距和斜率相同的点都存在一个集合中。然后找出最大的集合，最大的集合可能有多个。然后把集合转为数组，按照点的下标进行排序。而后根据数组中前两个点的下标，对所有数组排序。结果就是第一个数组中的前两个点。
class Solution {
public:
vector<int> bestLine(vector<vector<int>>& points) {
unordered_map<string, unordered_set<int>> key_to_points;
// 按截距和斜率把点分组存放
for(int i=0;i<points.size()-1;i++) {
vector<int> &p1 = points[i];
for (int j = i + 1; j < points.size(); j++) {
vector<int> &p2 = points[j];
string key = slope(p1, p2);
key += "_" + intercept(p1, p2);
key_to_points[key].insert(i);
key_to_points[key].insert(j);
}
}
// 找到最大集合的 size
int max_size = max_element(key_to_points.begin(), key_to_points.end(), [](auto& a, auto& b){
return a.second.size() < b.second.size();
})->second.size();
// 取出最大的集合，可能有多个
vector<vector<int>> max_size_points;
for_each(key_to_points.begin(), key_to_points.end(), [&max_size,&max_size_points](auto& a){
if(a.second.size() == max_size){
max_size_points.emplace_back(a.second.begin(), a.second.end());
sort(max_size_points.back().begin(), max_size_points.back().end());
}
});
// 对集合排序
sort(max_size_points.begin(), max_size_points.end(), [&key_to_points](auto& points1, auto& points2){
if(points1[0] < points2[0]){
return true;
}
if(points1[0] > points2[0]){
return false;
}
if(points1[1] < points2[1]){
return true;
}
return false;
});
return {max_size_points[0][0], max_size_points[0][1]};
}
string slope(vector<int> &p1, vector<int> &p2){
double x_diff = p1[0] - p2[0];
double y_diff = p1[1] - p2[1];
string s;
if (x_diff == 0) {
s = "inf";
}else if (y_diff == 0) {
s = "0";
}else{
double k = y_diff / x_diff;
s = to_string(k);
}
return s;
}
string intercept(vector<int> &p1, vector<int> &p2){
double x_diff = p1[0] - p2[0];
double y_diff = p1[1] - p2[1];
string s;
if (x_diff == 0) {
s = to_string(p1[0]);
}else if (y_diff == 0) {
s = to_string(p1[1]);
}else{
double b = p1[1] - (y_diff / x_diff) * p1[0];
s = to_string(b);
}
return s;
}
};