题号面试题16.14 最佳直线题目内容给定一个二维平面及平面上的 N 个点列表Points其中第i个点的坐标为Points[i][Xi,Yi]。请找出一条直线其通过的点的数目最多。设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S你仅需返回[S[0],S[1]]作为答案若有多条直线穿过了相同数量的点则选择S[0]值较小的直线返回S[0]相同则选择S[1]值较小的直线返回。注2 len(Points) 300len(Points[i]) 2示例输入[[0,0],[1,1],[1,0],[2,0]]输出[0,2]解释所求直线穿过的3个点的编号为[0,2,3]解题过程与思路本题采用暴力循环方式和优化方式暴力循环思路题目要求一条穿过最多点的直线对于给定起始点可以利用剩余点与起始点连成的直线的斜率是否相等来进行判断因为给定一点和斜率能唯一确定一条直线点斜式。具体实现过程可以从给定点集的第一点开始一层循环遍历剩余的点两层循环先确定一条直线再循环遍历所有点三层循环如果斜率相等则加入结果集。遍历结束后判断本次与上次结果集的长度编号决定保留还是丢弃。使用python编写代码如下def best_line(points: List[List[int]]) - List[int]: s [] for i in range(len(points) - 1): # 只需要遍历到倒数第二个点即可 for j in range(i 1, len(points)): # 选取剩下还没有当过起始点的点 temp [] delta_x points[j][0] - points[i][0] # 计算横坐标差 if delta_x 0: # 考虑斜率不存在的情况 for index in range(len(points)): if points[index][0] points[i][0]: # 横坐标相同加入到列表中 temp.append(index) else: temp.append(i) # 添加起始点 k (points[j][1] - points[i][1]) / delta_x # 计算斜率 for index in range(len(points)): if points[index][0] points[i][0]: # 斜率不存在跳过 continue if k (points[index][1] - points[i][1]) / (points[index][0] - points[i][0]): # 斜率相同加入到列表中 temp.append(index) temp.sort() # 升序排序便于比较编号 if len(temp) len(s): # 对比列表长度 s temp if len(temp) len(s): # 对比编号 if temp[0] s[0] or (temp[0] s[0] and temp[1] s[1]): s temp return [s[0], s[1]]可以看到上述代码使用了三层循环运行效率极慢并且需要处理复杂的边界条件显然不够优雅让我们从头开始优化思路。今天先写到这里先过周末祝大家周末愉快