鱼C论坛

 找回密码
 立即注册
查看: 3224|回复: 1

[技术交流] C++刷leetcode(面试题 16.14. 最佳直线)【数学】

[复制链接]
发表于 2021-4-9 21:13:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:

  1. 给定一个二维平面及平面上的 N 个点列表Points,其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线,其通过的点的数目最多。

  2. 设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S,你仅需返回[S[0],S[1]]作为答案,若有多条直线穿过了相同数量的点,则选择S[0]值较小的直线返回,S[0]相同则选择S[1]值较小的直线返回。

  3. 示例:

  4. 输入: [[0,0],[1,1],[1,0],[2,0]]
  5. 输出: [0,2]
  6. 解释: 所求直线穿过的3个点的编号为[0,2,3]
  7. 提示:

  8. 2 <= len(Points) <= 300
  9. len(Points[i]) = 2
复制代码


  1. class Solution {
  2. public:
  3.     vector<int> bestLine(vector<vector<int>>& points) {
  4.         vector<int>res(2);
  5.         int len = points.size();
  6.         int max_len = 0;
  7.         for(int i = 0; i < len-1; i++){
  8.             map<double, vector<int> >store;
  9.             double max_temp = 0;
  10.             for(int j = i+1; j < len; j++){
  11.                 double temp;
  12.                 if(points[i][1] - points[j][1] == 0){
  13.                     temp = 0.0;

  14.                 }else if(points[i][0] - points[j][0] == 0){
  15.                     temp = (double)INT_MAX;

  16.                 }else{
  17.                     temp = (points[i][1] - points[j][1]) / (double)(points[i][0] - points[j][0]);
  18.                 }
  19.                 store[temp].push_back(j);
  20.                 if(store[temp].size() > max_len){
  21.                     if(store[temp].size() >= 1){
  22.                         res[0] = i;
  23.                         res[1] = store[temp][0];
  24.                     }
  25.                     max_len = store[temp].size();
  26.                     max_temp = temp;
  27.                 }
  28.             }
  29.         }
  30.         return res;
  31.     }
  32. };
复制代码



注意事项:直线斜率计算。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-4-9 21:16:28 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-13 15:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表