算法之数组——共直线的最多点数

直线上最多的点数

难度困难:smirk:

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

示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
算法之数组——共直线的最多点数

示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
算法之数组——共直线的最多点数

思路

首先需要确定两个点在一条直线上 —— 即可以通过斜率的来表示,如果一个点p1和另外两个点p2,p3都在一条直线上,那么必有 k(p1,p2) = k(p1,p3);
所以可以通过斜率来确定与该点在同一条直线上的个数 ,如下图

算法之数组——共直线的最多点数

p(0,0),与其余5个点形成的斜率分别为

(0,0) - (1,5) -> k = 5
(0,0) - (1,4) -> k = 4
(0,0) - (3,3) - (4,4) -> k = 1
(0,0) - (5,1) -> k = 0.2

通过上图可以发现共直线点数最多的是 以当前目标点 p(0,0),斜率为 1 的直线,其上加上本身共有三个点!所以我们可以对每个点维护一个记录斜率的哈希表!每次获取当前斜率下的点数并判断更新!最终获得该点形成所有斜率的直线中,点数最多的一条!:boom: :boom: :boom:

需要注意以下几点

  • 对于重复点的处理,例如目标点(0,0) 和 待比较点 (0,0)两个点,这时(0,0)可以与自身形成任意斜率的点,所以这个重复数量需要单独处理
  • 对于在同一竖线上的点集是无法计算他的斜率的,故应该单独用一个标记记录,比如 “inf”
  • 如何计算斜率才能更好地保证唯一性? 可以用dxdy 的最大公约数,将分子分母约分,这里并没有真正计算出其除法运算的结果,是因为为了避免除不尽而出现小数的不精确性!!!例如 : 3/9 和 3/7 这种,double类型的浮点数判断相等是有误差的,所以这我们就用斜率 的 最简形式(不能约分)的字符串来代表此唯一性的斜率,即 dx / gcd(dx,dy) + "/" + dy / gcd(dx,dy)

通过代码体会:

package ddx.December.day8;

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

//给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
public class Normal_149 {
    public static void main(String[] args) {
        int[][] points = new int[][]{
               // {1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}
                //{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}
                {0, 0}, {1, 1}, {1,-1}
        };
        maxPoints(points);
    }


    public static int maxPoints(int[][] points) {
        if (points == null || points.length == 0 || points[0] == null || points[0].length == 0) {
            return 0;
        }

        int len = points.length;
        int max = 1;
        for (int i = 0; i < len; i++) {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int repeat = 0;
            int cur_max = 0;
            HashMap<String, Integer> hashMap = new HashMap<>();//通过维护一个唯一性的斜率哈希!
            for (int j = i + 1 ; j < len; j++) {//从 i + 1开始,不需要再重复比较!
                //先拿到当前基准点的横纵坐标
                int x2 = points[j][0]; 
                int y2 = points[j][1];
                if (x1 == x2 && y1 == y2) {
                    //重复点可以为任何斜率!!!所以需要单独记录
                    repeat++;
                    continue;
                }
                if (x1 == x2) { //直线竖直!!!需要用特殊标记来记录 - "inf"
                    if (!hashMap.containsKey("inf")) {
                        hashMap.put("inf", 1);
                    } else {
                        hashMap.put("inf", hashMap.get("inf") + 1);
                    }
                    cur_max = Math.max(hashMap.get("inf"), cur_max); //因为和当前点处于竖线的点是无法计算斜率,所以需要提前比较当前直线上的点数
                    continue;
                }
                //准备计算斜率
                int dx = x2 - x1; 
                int dy = y2 - y1;
                int _gcd = gcd(dx, dy); //计算分子分母的最大公约数
                String k = (dy / _gcd) + "/" + (dx / _gcd); //使用最大公约数约分一下,保证斜率的唯一性,并用字符串记录,避免double类型的不精确
                if (!hashMap.containsKey(k)) {
                    hashMap.put(k, 1);
                } else {
                    hashMap.put(k, hashMap.get(k) + 1);
                }
                cur_max = Math.max(hashMap.get(k), cur_max); //不断更新以point[i]为目标点的最大值
            }
            max = Math.max(cur_max + repeat + 1, max); //每一轮下来都得更新 
            System.out.println(hashMap.toString());
        }

        System.out.println(max);
        return max;
    }

    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!