Leetcode: 149. 直线上最多的点数
题目描述
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
思路
思路1: 点斜法记录直线+hashMap
使用点斜法记录i与i+1开始的斜率值，保存最大值，并记录重复值，最后比较结果
代码
代码1
class Solution {
public int maxPoints(int[][] points) {
if (points.length < 3){
return points.length;
}
int duplicatedNum = 0;
int num = points.length;
int result = 0;
for(int i = 0;i < num - 1; i++){
if (points[i][0] != points[i + 1][0] || points[i][1] != points[i+1][1]){
break;
}
duplicatedNum += 1;
}
if (duplicatedNum - 1 == num){
return num;
}
for(int i = 0; i < num - 1; i++){
duplicatedNum = 0;
Map tempMap = new HashMap<>();
int tempMax = 0;
for(int j = i + 1; j < num; j++){
int x = points[i][0] - points[j][0];
int y = points[i][1] - points[j][1];
int tempGcb = gcb(x, y);
if (x == 0 && y == 0){
duplicatedNum += 1;
continue;
}
x = x / tempGcb;
y = y / tempGcb;
String tempKey = x + "#" + y;
if (!tempMap.containsKey(tempKey)){
tempMap.put(tempKey, 0);
}
tempMap.put(tempKey, tempMap.get(tempKey) + 1);
if (tempMap.get(tempKey) > tempMax){
tempMax = tempMap.get(tempKey);
}
}
if (tempMax + duplicatedNum + 1 > result){
result = tempMax + duplicatedNum + 1;
}
}
return result;
}
private int gcb(int a, int b){
while(b != 0){
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}
复杂度分析
思路1时间复杂度
$O(n^2)$
思路1空间复杂度
$O(n^2)$
