直线上最多的点数
给定一个二维平面，平面上有 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
class Solution {
public int maxPoints(Point[] points) {
if(points.length == 0) {
return 0;
}
int[] count = new int[points.length];
for (int i = 0; i < points.length; i++) {
count[i] = 1;
int size = 1;
int same = 0;
HashMap<Integer[], Integer> hashMap = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if(i != j) {
if(points[i].x != points[j].x) {
int dy = points[i].y - points[j].y;
int dx = points[i].x - points[j].x;
int gcd = generateGCD(dy, dx);
if(gcd != 0) {
dy = dy / gcd;
dx = dx / gcd;
}
Integer[] nums = new Integer[2];
nums[0] = dy;
nums[1] = dx;
boolean flag = false;
for (Integer[] array : hashMap.keySet()) {
if(nums[0] == array[0] && nums[1] == array[1]) {
flag = true;
hashMap.put(array, hashMap.get(array) + 1);
}
}
if(!flag) {
hashMap.put(nums, 1);
}
}else {
if(points[i].y == points[j].y) {
same++;
}
size++;
}
}
}
for (Integer[] array : hashMap.keySet()) {
if(hashMap.get(array) + 1 > count[i]) {
count[i] = hashMap.get(array) + 1;
}
}
count[i] += same;
count[i] = Math.max(count[i], size);
}
int maxIndex = 0;
for (int i = 1; i < count.length; i++) {
if(count[i] > count[maxIndex]) {
maxIndex = i;
}
}
return count[maxIndex];
}
// 欧几里得算法：计算最大公约数
private int generateGCD(int x, int y) {
if (y == 0)
return x;
return generateGCD(y, x % y);
}
}
