Day74 直线上最多的点数

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

https://leetcode-cn.com/problems/max-points-on-a-line/

示例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

Java解法

思路：

• 今天刚看了关于动态规划的介绍在这里可以运用下动态规划的解题方法

• 先思考暴力解法

  • 第一个点；1个，横纵坐标等差0，不需要记录，至少有一个
  • 第二个点：2个(得到成立的横纵坐标关系)
  • 第三个点：2个或 3个(横纵坐标满足等差关系)
  • 第四个点: 2个或 3/4个(横纵坐标满足等差关系)
  • 第N个点: 2....N个(横纵坐标满足等差关系)

• 确定状态

  • N点 的解集为 N-1中 直线+1（满足拥有等差关系）}
  • f(n) = {1,n=1;max(List(d(n)),n>1} d(n)=横纵坐标等差比的直线

• 我想多了，拿着锤子看啥都是钉子,换个思路，记录所有的直线，挑出最多点的直线返回

• 新增点时，对已有直线进行遍历操作

  • 这里主要解决如何将点归属为一条直线，答案是斜率与原点的偏移量
  • (x-x1)/(x1-x2)=(y-y1)/(y1-y2) 表示通过x，y的直线方程
  • 通过一般式 y=kx+c 来细分每一条直线，早知道直接从初中数学入手，脑子不行了
  • 利用hashset避免重复添加

  我对水平、垂直线做了特殊记录，实际可以囊括处理

package sj.shimmer.algorithm.m4_2021;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * Created by SJ on 2021/4/11.
 */

class D74 {
    public static void main(String[] args) {
        System.out.println(maxPoints(new int[][]{{1, 1}, {2, 2}, {3, 3}, {4, 4}}));
        System.out.println(maxPoints(new int[][]{{0, 0}, {1, -1}, {1, 1}}));
        System.out.println(maxPoints(new int[][]{{2, 3}, {3, 3}, {-5, 3}}));
        System.out.println(maxPoints(new int[][]{{0, 0}, {4, 5}, {7, 8}, {8, 9}, {5, 6}, {3, 4}, {1, 1}}));
    }

    public static int maxPoints(int[][] points) {
        if (points == null) {
            return 0;
        }
        int length = points.length;
        if (length < 3) {
            return length;
        }
        int result = 2;

        HashMap<Double, HashMap<Double,HashSet<int[]>>> map = new HashMap<>();
        HashMap<Integer, HashSet<int[]>> horLineMap = new HashMap<>();
        HashMap<Integer, HashSet<int[]>> verLineMap = new HashMap<>();

        for (int i = 1; i < length; i++) {
            //与之前的点相连
            for (int j = 0; j < i; j++) {

                int x1 = points[i][0];
                int x2 = points[j][0];
                int y1 = points[i][1];
                int y2 = points[j][1];

                int x = x1 - x2;
                int y = y1 - y2;
                if (x == 0) {
                    HashSet<int[]> vL = verLineMap.get(x1);
                    if (vL == null) {
                        vL = new HashSet<>();
                        vL.add(points[j]);
                    }
                    vL.add(points[i]);
                    verLineMap.put(x1, vL);
                } else if (y == 0) {
                    HashSet<int[]> hL = horLineMap.get(y1);
                    if (hL == null) {
                        hL = new HashSet<>();
                        hL.add(points[j]);
                    }
                    hL.add(points[i]);
                    horLineMap.put(y1, hL);
                } else {

                    //两点式 (x-x1)/(x1-x2)=(y-y1)/(y1-y2)   y = (x-x1)*(y1-y2)/(x1-x2) +y1
                    //一般直线 式 y = kx+c
                    double k = 1.0 * x / y;
                    //当x=0时，通过两点式求出y，即为一般式中的c
                    double c = (0-x1)*y/x +y1;
                    HashMap<Double, HashSet<int[]>> lineMap = map.getOrDefault(k, new HashMap<>());
                    HashSet<int[]> l = lineMap.get(c);
                    if (l == null) {
                        l = new HashSet<>();
                        l.add(points[j]);
                    }
                    l.add(points[i]);
                    lineMap.put(c, l);
                    map.put(k, lineMap);
                }
            }
        }
        for (Map.Entry<Double, HashMap<Double,HashSet<int[]>>> entry : map.entrySet()) {
            for (Map.Entry<Double, HashSet<int[]>> line : entry.getValue().entrySet()) {
                result = Math.max(line.getValue().size(), result);
            }
        }
        for (Map.Entry<Integer, HashSet<int[]>> entry : horLineMap.entrySet()) {
            result = Math.max(entry.getValue().size(), result);
        }
        for (Map.Entry<Integer, HashSet<int[]>> entry : verLineMap.entrySet()) {
            result = Math.max(entry.getValue().size(), result);
        }
        return result;
    }
}

image

官方解

https://leetcode-cn.com/problems/max-points-on-a-line/solution/zhi-xian-shang-zui-duo-de-dian-shu-by-leetcode/

1. 枚举

   关于直线区分参考了下这个答案，但考虑当前点的思路暂时没有理清楚，有兴趣可以详读一下

   image

   • 时间复杂度：O(N^2 )
   • 空间复杂度：O(N)