class Solution {
public:
vector<int> bestLine(vector<vector<int>>& points) {
}
};
面试题 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) <= 300len(Points[i]) = 2原站题解
golang 解法, 执行用时: 44 ms, 内存消耗: 6.8 MB, 提交时间: 2022-11-30 20:47:14
func bestLine(points [][]int) []int {
max := 0
ans := []int{0, 1}
for i := 0; i < len(points)-max; i++ {
//记录这个斜率的第二个点
second := make(map[float32]int)
//记录这个斜率的个数
amount := make(map[float32]int)
o := points[i]
for j := i + 1; j < len(points); j++ {
//斜率（默认为最大，如果不在同一y轴则计算）
slope := float32(math.MaxFloat32)
if float32(points[j][1]-o[1]) != 0 {
slope = float32(points[j][0]-o[0]) / float32(points[j][1]-o[1])
}
if second[slope] == 0 {
second[slope] = j
}
amount[slope]++
if amount[slope] > max {
ans = []int{i, second[slope]}
max = amount[slope]
} else if amount[slope] == max {
if ans[0] > i || ans[0] == i && ans[1] > second[slope] {
ans = []int{i, second[slope]}
}
} else {
continue
}
}
}
return ans
}
python3 解法, 执行用时: 228 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-30 20:36:38
'''
考虑通过每个点的所有直线（和这个点之后的所有点形成的线段斜率），使用最大公约数归一化斜率为分数
'''
class Solution:
def bestLine(self, points):
n = len(points)
def gcd(a, b):
while a:
a, b = b % a, a
return b
max_points, res = 0, None
for i in range(n):
slopes = {}
for j in range(i + 1, n):
dx, dy = points[j][0] - points[i][0], points[j][1] - points[i][1]
g = gcd(dx, dy)
slope = (dx // g, dy // g)
if slope in slopes:
slopes[slope][0] += 1
else:
slopes[slope] = [1, (i, j)]
if slopes[slope][0] > max_points:
max_points = slopes[slope][0]
res = slopes[slope][1]
elif slopes[slope][0] == max_points:
if slopes[slope][1] < res:
res = slopes[slope][1]
else:
continue
return res
cpp 解法, 执行用时: 236 ms, 内存消耗: 8 MB, 提交时间: 2022-11-30 18:53:11
class Solution {
public:
vector<int> bestLine(vector<vector<int>>& points) {
int n = points.size();
// 保存最大的数量和对应的序号数组
int maxCnt = 0;
vector<int> res(2, 0);
for (int i = 0; i < n; ++i)
{
for (int j = i+1; j < n; ++j)
{
int cnt = 2;
// 坑： 这里计算需要用long避免乘法时候的溢出
long x1 = points[i][0] - points[j][0];
long y1 = points[i][1] - points[j][1];
for (int k = j + 1; k < n; ++k)
{
long x2 = points[i][0] - points[k][0];
long y2 = points[i][1] - points[k][1];
if (x1*y2 == x2*y1)
{
++cnt;
}
}
if (cnt > maxCnt)
{
maxCnt = cnt;
res[0] = i;
res[1] = j;
}
}
}
return res;
}
};
python3 解法, 执行用时: 136 ms, 内存消耗: 15 MB, 提交时间: 2022-11-30 18:52:43
class Solution:
def bestLine(self, points: List[List[int]]) -> List[int]:
ansnum, n = 0, len(points)
ans = []
for i in range(n):
x, y = points[i]
_dict = defaultdict(list)
for j in range(i+1, n):
tx, ty = points[j]
if tx == x:
_dict['inf'].append(j)
else:
k = (ty - y) / (tx - x)
_dict[k].append(j)
for k in _dict:
if len(_dict[k]) + 1 > ansnum:
ans = [i] + _dict[k]
ansnum = len(_dict[k]) + 1
return ans[0: 2]