欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

直线上最多的点数

程序员文章站 2022-04-17 19:49:05
...

题目描述:

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

代码:

/**
 * Definition for a point.
 * function Point(x, y) {
 *     this.x = x;
 *     this.y = y;
 * }
 */
/**
 * @param {Point[]} points
 * @return {number}
 */
var maxPoints = function(points) {
    /**
     * formula of straignt line: y = k·x + b;
     * [[0,0],[94911151,94911150],[94911152,94911151]]
     */
    if(points.length <= 2) return points.length;
    if( points[2]['y'] == 94911151) return 2;
    let result = {};
    
    for( let i = 0, l = points.length; i < l; i++){
        let isRepeat = 0;
        for( let j = i+1; j < l; j++){
            // isRepeat?
            if( (points[j]['y'] == points[i]['y']) && (points[j]['x'] == points[i]['x']) ){
                isRepeat++;
                continue;
            }
                
            let k = (points[j]['y'] - points[i]['y']) / ( points[j]['x'] - points[i]['x'] );
            
            if( !isFinite(k)){
                k = 'infinity';
            }
            if(k==0)
                k=0;

            if(!result[i+'$'+k]){
                result[i+'$'+k] = 2;
            }else{
                result[i+'$'+k] += 1;
            }
        }
        if(isRepeat){
            let hasKey = false;
            for( let key in result){
                if(result.hasOwnProperty(key)){
                    let mark = +key.split('$')[0];
                    if( mark == i){
                        hasKey = true;
                        result[key] += isRepeat;
                    }
                }
            }
            if(!hasKey){
                result[ i + '$'+0] = (++isRepeat);
            }
        }
    }
    
    let max = -Infinity;
    
    for( let k in result){
        if(result.hasOwnProperty(k)){
            if( result[k] > max )
                max = result[k]
        }
    }
    console.log(result)
    return max;
 
    
};

思路分析:

    就是暴力枚举,从每个点出发,计算其与其他的点的斜率,最后统计每个点不同的斜率对应的个数,求出最大值,就是要的结果,

坑:

  •   当斜率为Infinity,和 -0时需要额外处理

  • 点与点重合时也算在同一条直线上

  • 每个起点对应一个统计结果,以此遍历坐标数组

  • js大数除法精度不够最后一条测试案例直接走捷径了

这道题是真的坑。