leetcode-149-直线上最多的点数

[博客链接]

一个菜🐔的学习之路

掘金首页

[题目描述]

  1. 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 
  5.  示例 1： 
  8. 输入：points = [[1,1],[2,2],[3,3]]
  9. 输出：3
  12.  示例 2： 
  15. 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
  16. 输出：4
  21.  提示： 
  24.  1 <= points.length <= 300 
  25.  points[i].length == 2 
  26.  -10^4 <= xi, yi <= 10^4
  27.  points 中的所有点 互不相同 
  29.  Related Topics 几何 哈希表 数学 
  30.  👍 275 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：hash + 枚举

  • 枚举每条线路的斜率k和截距b，通过double进行记录(考虑斜率不为整型的情况)
  • 考虑水平线和竖直线，水平线斜率为0，不影响运算，竖直线因为斜率为最大值，我们用Integet.MAXVALUE进行替代
  • 然后通过斜率+截距作为map的key，然后value为节点索引，最后索引+1即为在这条直线上的节点数
  • 因为有可能有斜率为负数0（-0.0）的情况所以需要对这种特殊情况做个判断
  • 当节点数小于2的时候，根据公理，两点能确定一条直线可以直接返回节点数
  1.         public int maxPoints(int[][] points) {
  2.             //corner case
  3.             if (points.length <=2){
  4.                 return points.length;
  5.             }
  6.             int max = 2;
  7.             for (int i = 0; i < points.length; i++) {
  8.                 Map<String, List<Integer>> map = new HashMap<>();
  9.                 for (int j = i + 1; j < points.length; j++) {
  10.                     //水平和垂直线（）
  11.                     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]);
  12.                     double b = k == Integer.MAX_VALUE ? Integer.MAX_VALUE : (points[i][1] - k * points[i][0]);
  14.                     String key = k == (-0.0)? "0.0":k + "," + b;
  15.                     List<Integer> list = map.getOrDefault(key, new ArrayList<>());
  16.                     list.add(j);
  17.                     map.put(key, list);
  18.                 }
  19.                 for (Map.Entry<String, List<Integer>> entry : map.entrySet()
  20.                 ) {
  21.                     max = Math.max(max, entry.getValue().size() + 1);
  22.                 }
  23.             }
  25.             return max;
  26.         }

时间复杂度在我来看是O(n^2)