LeetCode 面试题 16.14. 最佳直线-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 16.14. 最佳直线。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

给定一个二维平面及平面上的 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

点击此处跳转题目。

二、C# 题解

暴力枚举，效果反而是最好的hh。注意以下几点：文章来源地址https://www.toymoban.com/news/detail-739965.html

使用 x1 * y2 == x2 * y1 判断斜率是否相同。
少封装方法，以免传参影响计算效率。

public class Solution {
    public int[] BestLine(int[][] points) {
        int   max = 0;
        int[] ans = { 0, 1 };
        for (var i = 0; i < points.Length; i++) {
            for (var j = i + 1; j < points.Length; j++) {
                int tmp = 0;
                int x1  = points[i][0] - points[j][0], y1 = points[i][1] - points[j][1];
                for (int k = j + 1; k < points.Length; k++) {
                    int x2 = points[k][0] - points[j][0], y2 = points[k][1] - points[j][1];
                    if (x1 * y2 == x2 * y1) tmp++;
                }
                if (tmp <= max) continue;
                max = tmp;
                ans[0] = i;
                ans[1] = j;
            }
        }
        return ans;
    }
}