二刷 07/2022
Version #1 Calculate the slope of each point
还是看了答案好久才做出来
思路就是计算通过某一个点的所有线的slope，存到map里面，然后求最大
slope用分数表示因为double精度不够
Time O(N^2)
Space O(N)
Runtime: 38 ms, faster than 58.30% of Java online submissions for Max Points on a Line.
Memory Usage: 46.6 MB, less than 67.92% of Java online submissions for Max Points on a Line.
class Solution {
public int maxPoints(int[][] points) {
int max = 0;
for (int i = 0; i < points.length; i++) {
Map<Pair<Integer, Integer>, Integer> count = new HashMap<>();
int currMax = 0;
int dup = 1;
for (int j = i + 1; j < points.length; j++) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
dup++;
continue;
}
// calculate a slope represents the line of points[i] and points[j]
Pair<Integer, Integer> slope = getSlope(points[i], points[j]);
int slopeCnt = count.getOrDefault(slope, 0) + 1;
currMax = Math.max(currMax, slopeCnt);
count.put(slope, slopeCnt);
}
max = Math.max(max, currMax + dup);
}
return max;
}
private Pair<Integer, Integer> getSlope(int[] p, int[] q) {
int dy = p[1] - q[1];
int dx = p[0] - q[0];
if (dx == 0) {
return new Pair<>(Integer.MAX_VALUE, Integer.MAX_VALUE);
}
if (dy == 0) {
return new Pair<>(0, 0);
}
int gcd = getGCD(dy, dx);
return new Pair<>(dy / gcd, dx / gcd);
}
private int getGCD(int a, int b) {
if (b == 0) {
return a;
}
return getGCD(b, a % b);
}
}
看见数学题就脑袋疼
这里用一个hashmap存斜率和count的映射，因为受精度的限制，存成<x, <y, count>> 的映射
Time O(n^2)
Space O(n)
"The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. "
How to find GCD of two numbers in Java - Euclid's algorithm Read more: http://www.java67.com/2012/08/java-program-to-find-gcd-of-two-numbers.html#ixzz4pcHqFs76
90.73 %
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points == null) return 0;
if (points.length <= 2) return points.length;
int maxCount = 2;
//key-diffX, value-Map<key-diffY, value-count>
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
//start (x0, y0) end (x1, y1) (x2, y2)
//looking for (x2, y2) where (y1-y0)/(x1-x0) == (y2-y0)/(x2-x0)
for (int start = 0; start < points.length; start++) {
map.clear();
int overlap = 0;
int currMax = 0;
//start point it self is count as 1 point
for (int end = start; end < points.length; end++) {
int diffX = points[end].x - points[start].x;
int diffY = points[end].y - points[start].y;
if (diffX == 0 && diffY == 0) {
overlap++;
continue;
}
int gcd = generateGCD(diffX, diffY);
if (gcd != 0) {
diffX = diffX / gcd;
diffY = diffY / gcd;
}
if (!map.containsKey(diffX)) map.put(diffX, new HashMap<Integer, Integer>());
Map<Integer, Integer> countMap = map.get(diffX);
int currCount = 1;
if (countMap.containsKey(diffY)) currCount = countMap.get(diffY) + 1;
countMap.put(diffY, currCount);
currMax = Math.max(currMax, currCount);
}
maxCount = Math.max(maxCount, currMax + overlap);
}
return maxCount;
}
private int generateGCD(int a, int b) {
if (b == 0) return a;
return generateGCD(b, a % b);
}
}
No comments:
Post a Comment