Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.



Naive Way: 每两个点确定一条直线 ，每确定一条直线遍历所有点，每次用经过的点个数和最大值作比较。这样的话就需要O(n^3) run time。其中，有直线平行于x-axis或y-axis，两个点重叠的edge case可能会造成遗漏。并且考虑到k和b是小数可能带来误差，比较时采用取差值在一定小的范围内的方法。


/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    static final double zero = 0.0001;
    public int maxPoints(Point[] points) {
    // O(n^3)
        int max = 1;
        for(int i = 0;i < points.length-1;i++){
            for(int j = i+1;j < points.length;j++){
                int count = 0;
                // case 1: no y parallel
                if(points[i].x!=points[j].x){
                    double k = (points[i].y - points[j].y)/(double)(points[i].x-points[j].x);
                    double b = (double)points[i].y - k*points[i].x;
                    for(int t = 0;t < points.length;t++){
                        if(Math.abs(k*points[t].x+b-points[t].y) < zero)
                            count++;
                    }
                    max = Math.max(max, count);
                }else{ // case 2: parallel to y axis
                    for(int t = 0;t < points.length;t++){
                        if(points[t].x == points[i].x)
                            count++;
                    }
                    max = Math.max(max, count);
                }
            }
        }
        return points.length==0?0:max;
    }
}

Improved Way: 由于最坏的情况是没有三个点在同一条直线上，那么至少需要运行O(n^2)次来遍历所有可能的直线，所以最低的run time应该也要O(n^2)。 一个比较直观的感觉就是如果可以记录每一条直线，存入一个Map中，每次得到新的直线都先看Map中是否已有，有就增加Map的value，没有就加入新的直线，该法基于Map可以O(1)的读存， 使run time 提升到O(n^2),但同时也带来了O(n^2)的extra space.

但其实这种方法有难度，难在如何记录一条直线上。我自己想到的方法是构建一个新类表示一条线。采用两个参数 k 和 b, 分别表示 y = kx+b中中的两个参数。这样会带来一个问题，表示x = c时会无法表示。可以多设立一个c参数和一个boolean值来区分是否是平行于x-axis。

这里写的时候才发现了另一个问题，同样参数的两个新类，Map不会设别成同一个Key，必须得自己重写equals函数和hashCode函数，具体我是看了一个教程教你如何用Java写Equal函数 How to Write a Equality Method in Java，很有用， 具体自己的hashCode函数是rounding的，肯定很有误差，但是估计leetcode的样本很少，还是能通过。




public class Solution {
        static final double zero = 0.0001;
        public int maxPoints(Point[] points) { 
            // O(n^2)
            int max = 1;
        Map<Line, Set<Integer>> map = new HashMap<Line, Set<Integer>>();
        for(int i = 0; i < points.length-1;i++){
            for(int j = i+1; j < points.length;j++){
                if(points[i].x==points[j].x){
                    Line line = new Line(points[i].x);
                    if(!map.containsKey(line)){
                        Set<Integer> set = new HashSet<Integer>();
                        set.add(i);
                        set.add(j);
                        map.put(line, set);
                    }else{
                        Set<Integer> set = map.get(line);
                        set.add(i);
                        set.add(j);
                        map.put(line, set);
                    }
                }else{
                    double k = (points[i].y - points[j].y)/(double)(points[i].x-points[j].x);
                    double b = (double)points[i].y - k*points[i].x;
                    Line line = new Line(k,b);
                    if(!map.containsKey(line)){
                        Set<Integer> set = new HashSet<Integer>();
                        set.add(i);
                        set.add(j);
                        map.put(line, set);
                    }else{
                        Set<Integer> set = map.get(line);
                        set.add(i);
                        set.add(j);
                        map.put(line, set);
                    }
                }
            }
        }
        for(Map.Entry<Line, Set<Integer>> entry: map.entrySet())
            max = Math.max(max, entry.getValue().size());
        return points.length==0?0:max;
        }
       
        class Line{
            double k;
            double b;
            boolean xp;
            int xValue;
            Line(double m, double n){
                k = m;
                b = n;
                xp = false;
                xValue = 0;
            }
            Line(int v){
                k = Integer.MAX_VALUE;
                b = 0;
                xp = true;
                xValue = v;
            }
            @Override
            public int hashCode(){
                return (int)Math.round(k) << 16|(int)Math.round(b) + xValue;
            }
            @Override
            public boolean equals(Object o){
                if(o == this)
                    return true;
                if(!(o instanceof Line))
                    return false;
                Line l = (Line)o;
                if(xp && l.xp)
                    return xValue==l.xValue;
                else
                    return Math.abs(k-l.k) < zero && Math.abs(b-l.b) < zero;
            }
        }
    }



Other Ways: 在网上看到一个很好的方法，是采用两个Map和找最大公约数。对于一条直线y=kx+b, 每次得到k和b通过求他们最大公约数可以把他们化成最小量值，这样再次出现一样斜率的直线，就可以找相同的k，那么第一个map就是 k->b 的map。每一个斜率对应不同偏量。 第二个map就是 b->#points 的map， 每个确定的直线对应点的个数，最后就是一个Map<Integer, Map<Integer, Integer>>的形式，在这里，大家可以去看一看具体的code，写得好呀。