LeetCode_ Hash table_ Difficulties_ 149. Maximum number of points on the line

1. subject

Give you an array points , among points[i] = [x_i, y_i] Express X-Y A point on the plane . Find out how many points are in the same line at most .

Example 1：

Input ：points = [[1,1],[2,2],[3,3]]
Output ：3

Example 2：

Input ：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output ：4

Tips ：
1 <= points.length <= 300
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
points All points in are different from each other

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/max-points-on-a-line

2. Ideas

（1） The law of violent exhaustion
Violent exhaustion is easier to think of , Because two different points in the plane can determine a straight line , So you can First enumerate the combination of two points （ That is to determine a straight line ）, Then check whether the remaining points are on the straight line .

（2） Improvement of violent exhaustion _ Hashtable
Train of thought reference The user's question solution .
Because two points determine a straight line , So we can enumerate all the possible slope of the straight line （ That is, enumerate all point pairs ）, Then use the hash table to count the number of points on the straight line corresponding to all slopes （ Instant key / value = Slope / The number of points ）, Then the maximum of all values is the answer .

3. Code implementation （Java）

// Ideas 1———— The law of violent exhaustion 
class Solution {
    
    public int maxPoints(int[][] points) {
    
        // At most  cnt  The points are on the same straight line , because  1 <= points.length <= 300, therefore  cnt  The initial value of  1
        int cnt = 1;
        int n = points.length;
        for (int i = 0; i < n; i++) {
    
            int[] p1 = points[i];
            for (int j = i + 1; j < n; j++) {
    
                int[] p2 = points[j];
                //p1  And  p2  It must be in a straight line , So at least  2  The points are on the same straight line 
                int tmpCnt = 2;
                for (int k = j + 1; k < n; k++) {
    
                    int[] p3 = points[k];
                    /* (1)  If  (p1[1] - p2[1])/(p1[0] - p2[0]) == (p2[1] - p3[1])/(p2[0] - p3[0])  that  p1、p2、p3  this  3  The points are on the same straight line  (2)  In order to prevent the loss of accuracy when dividing integers , So change the above equation to ： (p1[0] - p2[0]) * (p2[1] - p3[1]) = (p1[1] - p2[1]) * (p2[0] - p3[0]) */
                    if ((p1[0] - p2[0]) * (p2[1] - p3[1]) == (p1[1] - p2[1]) * (p2[0] - p3[0])) {
    
                        tmpCnt++;
                    }
                }
                cnt = Math.max(tmpCnt, cnt);
            }
        }
        return cnt;
    }
}

// Ideas 2———— Improvement of violent exhaustion _ Hashtable 
class Solution {
    
    public int maxPoints(int[][] ps) {
    
        int n = ps.length;
        int cnt = 1;
        for (int i = 0; i < n; i++) {
    
            Map<String, Integer> hashMap = new HashMap<>();
            //  From the current point  i  The maximum number of points passed by the emitted straight line 
            int max = 0;
            for (int j = i + 1; j < n; j++) {
    
                int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
                max = Math.max(max, hashMap.get(key));
            }
            cnt = Math.max(cnt, max + 1);
        }
        return cnt;
    }
    
    // seek  a  and  b  Maximum common divisor of 
    public int gcd(int a, int b) {
    
        return b == 0 ? a : gcd(b, a % b);
    }
}