Leetcode -149- The most points on a line

This is the second day of my participation in the More text Challenge. For more details, see more text Challenge

[Blog link]

A way to learn ๐Ÿ”

The nuggets home page

[Topic description]

You are given an array points, where points[I] = [xi, yi] represents a point in the X-y plane. Find the maximum number of points on the same line. The sample1: Enter: points = [[1.1], [2.2], [3.3]] output:3The sample2: Enter: points = [[1.1], [3.2], [5.3], [4.1], [2.3], [1.4]] output:4Tip:1 <= points.length <= 300 
 points[i].length == 2 
 -10^4 <= xi, yi <= 10^4All points in points are different from each other Related Topics Geometric hash table mathematics ๐Ÿ‘275 ๐Ÿ‘Ž 0

Copy the code

[Topic link]

Leetcode title link

[making address]

Code link

[ๆ€่ทฏไป‹็ป]

Idea 1: Hash + enumeration

  • Enumerates the slope k and the intercept b of each line, using double (if the slope is not an integer)
  • Consider the horizontal line and the vertical line. The horizontal line has a slope of 0, so it doesn’t affect the calculation. The vertical line has a maximum slope, so we use Integet
  • Then the slope + intercept is the key of the map, the value is the index of the nodes, and the index +1 is the number of nodes along the line
  • Because it’s possible that ** has a negative slope of 0 (-0.0) ** so we need to make a judgment about this particular case
  • When the number of nodes is less than 2, according to the axiom, two points can determine a line that can directly return the number of nodes
        public int maxPoints(int[][] points) {
            //corner case
            if (points.length <=2) {return points.length;
            }
            int max = 2;
            for (int i = 0; i < points.length; i++) {
                Map<String, List<Integer>> map = new HashMap<>();
                for (int j = i + 1; j < points.length; j++) {
                    // Horizontal and vertical lines ()
                    double k = (points[i][0] - points[j][0= =])0 ? Integer.MAX_VALUE : (double)(points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
                    double b = k == Integer.MAX_VALUE ? Integer.MAX_VALUE : (points[i][1] - k * points[i][0]);

                    String key = k == (-0.0)? "0.0":k + "," + b;
                    List<Integer> list = map.getOrDefault(key, new ArrayList<>());
                    list.add(j);
                    map.put(key, list);
                }
                for (Map.Entry<String, List<Integer>> entry : map.entrySet()
                ) {
                    max = Math.max(max, entry.getValue().size() + 1); }}return max;
        }
Copy the code

The time complexity in my view is O(
n 2 n^2 )