【LeetCode】149. 直线上最多的点数

比眉伴天荒 2022-10-09 12:17 109阅读 0赞

> 2021.6.24号每日一题

### 文章目录 ###

*   *  题目链接
     *  题目简介
     *  题目解析
     *  题目代码

## 题目链接 ##

[149. 直线上最多的点数][149.]

## 题目简介 ##

给你一个数组 `points` ，其中 `points[i] = [xi, yi]` 表示 `X-Y` 平面上的一个点。求最多有多少个点在同一条直线上。

**示例 1：**  
![在这里插入图片描述][69c636b932676fa16d04cf33e5936743.png_pic_center]

输入：points = [[1,1],[2,2],[3,3]]
    输出：3

## 题目解析 ##

1.  给定一些点，求哪些点在一条直线上
2.  常见的做法有两种：
    
     *  第一种：计算每个点和其他点的斜率比`（y2 - y1）/ （x2 - x1）`，将斜率比按 `数值` 存进 `map`
     *  第二种：计算每个点和其他点的斜率比`（y2 - y1）/ （x2 - x1）`，将斜率比按 `字符串` 存进 `map`
3.  这里需要注意一下，我们在计算斜率的时候，会出现分母为0的情况，在C++中不影响程序的运行，但是在Java中是影响程序运行的。我们去看下Java官方关于这一块的定义：
    
        Thrown when an exceptional arithmetic condition has occurred. 
        For example, an integer "divide by zero" throws an instance of this class.
        当出现异常的运算条件时，抛出此异常。
        例如，一个整数“除以零”时，抛出此类的一个实例。
    
    所以，我们需要在我们整除的时候，将分子置为 `小数` 类型

## 题目代码 ##

class Solution {
        
        public int maxPoints(int[][] points) {
        
            if(points.length == 1){
        
                return 1;
            }
            int max = 0;
            for (int i = 0; i < points.length; i++) {
        
                int x = points[i][0];
                int y = points[i][1];
                HashMap<Double, Integer> map = new HashMap<>();
                for (int j = 0; j < points.length; j++) {
        
                    if (j != i) {
        
                        double target = ((points[j][1] - y) * 1.0)  / (points[j][0] - x);
                        
                        if (map.containsKey(target)) {
        
                            int value = map.get(target);
                            map.put(target, ++value);
                        } else {
        
                            map.put(target, 2);
                        }
                    }
                }
                
                for (Map.Entry<Double, Integer> entry : map.entrySet()) {
        
                    max = Math.max(max, entry.getValue());
                }
            }
            return max;
        }
    }

[149.]: https://leetcode-cn.com/problems/max-points-on-a-line/
[69c636b932676fa16d04cf33e5936743.png_pic_center]: /images/20221005/883a49d9162b42bca29ba285810a5ef7.png