leetCode-149:Max Points on a Line

问题描述

给定一个二维数组表示二维坐标系上的不同坐标，这些不同的坐标构成了很多条直线，要求直线上拥有最多的坐标数量。题目链接：**点我**

样例输入输出

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

输出：3

说明：这三个坐标都在同一条直线上

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

输出：4

说明：[3,2],[4,1],[2,3],[1,4] 这四个坐标在同一条直线上

问题解法

循环遍历每个坐标，针对每个坐标，找出其他坐标与这个坐标构成的直线，如果斜率相同，说明是同一条直线，则计数加一，同时更新最大的坐标数量。需要注意的是，斜率之间的比较不能使用 double 进行比较，因为这是不准确的，用 BigDecimal 进行比较规避此问题。代码如下

import java.math.BigDecimal;

class Solution
{
    public int maxPoints(int[][] points)
    {
        int count = 0;
        for (int i = 0; i < points.length; i++)
        {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int infiniteCount = 0;
            Map<BigDecimal, Integer> map = new HashMap<>();
            for (int j = i + 1; j < points.length; j++)
            {
                int x2 = points[j][0];
                int y2 = points[j][1];
                if (x1 == x2)
                {
                    infiniteCount++;
                    count = Math.max(count, infiniteCount);
                    continue;
                }
                double k = (y2 - y1) * 1.0 / (x2 - x1);
                int nums = map.getOrDefault(BigDecimal.valueOf(k), 0) + 1;
                count = Math.max(count, nums);
                map.put(BigDecimal.valueOf(k), nums);
            }
        }
        return count + 1;
    }
}