|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给定一个二维平面及平面上的 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
复制代码
- class Solution {
- public:
- vector<int> bestLine(vector<vector<int>>& points) {
- vector<int>res(2);
- int len = points.size();
- int max_len = 0;
- for(int i = 0; i < len-1; i++){
- map<double, vector<int> >store;
- double max_temp = 0;
- for(int j = i+1; j < len; j++){
- double temp;
- if(points[i][1] - points[j][1] == 0){
- temp = 0.0;
- }else if(points[i][0] - points[j][0] == 0){
- temp = (double)INT_MAX;
- }else{
- temp = (points[i][1] - points[j][1]) / (double)(points[i][0] - points[j][0]);
- }
- store[temp].push_back(j);
- if(store[temp].size() > max_len){
- if(store[temp].size() >= 1){
- res[0] = i;
- res[1] = store[temp][0];
- }
- max_len = store[temp].size();
- max_temp = temp;
- }
- }
- }
- return res;
- }
- };
复制代码
注意事项:直线斜率计算。 |
|