lintcode 中等题：Max Points on a Line 最多有多少个点在一条直线上

题目

最多有多少个点在一条直线上

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

样例

给出4个点：(1, 2), (3, 6), (0, 0), (1, 3)。

一条直线上的点最多有3个。

解题

直接暴力求解有问题，时间复杂度O(N³)，对其中的相同点没有处理，斜率为0，不存在也没有处理，找出运行不对

看到通过定义一个HashMap存储直线的斜率，存在相同的情况就+ 1 ，最后找到斜率个数最长的那个。

下面程序中已经有很多注释了。

 /**

 * 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 {

    /**

     * @param points an array of point

     * @return an integer

     */

    public int maxPoints(Point[] points) {

        // Write your code here

        if(points == null)

            return 0;

        int m = points.length;

        if(m == 0)

            return 0;

        if( m <= 2)

            return m;

        int maxline = 0;

        HashMap<Double,Integer> map = new  HashMap<Double,Integer>();

        for(int i = 0 ;i < m ; i ++){

            map.clear();

            // dup 是记录和当前点i相同的点的个数，注意这里不包括当前点 i

            int dup = 0;

            for(int j = i + 1; j < m ;j++){

                // 出来相同的点

                if(points[i].x == points[j].x && points[i].y == points[j].y){

                    dup ++;

                    continue;

                }

                // 处理斜率不存在的情况

                double k = points[i].x==points[j].x ?Integer.MAX_VALUE:

                (0.0+ points[i].y-points[j].y)/(points[i].x-points[j].x)*1.0;

                if(map.containsKey(k)){

                    map.put(k,map.get(k)+1); // 这里是新的j点，只需 + 1

                }else{

                    map.put(k,2); // i j 两个点所在的直线，有两个点

                }

            }

            // 全部相同的情况

            if(map.size()==0){

                    // 需要加上当前点

                    maxline = Math.max(maxline,dup + 1 );

            }else{

                for(int tmp:map.values()){

                    if(tmp+dup>maxline)

                        maxline = tmp+dup;

                }

            }

        }

        return maxline;

    }

}

Java Code

# Definition for a point.

# class Point:

#     def __init__(self, a=0, b=0):

#         self.x = a

#         self.y = b

class Solution:

    # @param {int[]} points an array of point

    # @return {int} an integer

    def maxPoints(self, points):

        # Write your code here

        if points == None :

            return 0

        m = len(points)

        if m <= 2:

            return m

        maxline = 0

        for i in range(m):

            dup =  1

            d = {}

            d['inf'] = 0

            for j in range((i+1),m):

                if points[i].x == points[j].x and points[j].y == points[i].y:

                    dup +=1

                elif points[j].x == points[i].x:

                    d['inf'] += 1

                else:

                    k = 1.0*(points[j].y - points[i].y)/(points[j].x - points[i].x)

                    if k in d:

                        d[k] += 1

                    else:

                        d[k] = 1

            maxline = max( max(d.values()) + dup,maxline)

        return maxline 

Python Code

lintcode 中等题：Max Points on a Line 最多有多少个点在一条直线上的相关教程结束。