HomeResumePostsNotesLeetcodesAboutgithub

直线上最多的点数

07/03/2021

leetcode-直线上最多的点数

题目描述

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：

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

提示：

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • points 中的所有点 互不相同

本人题解

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function(points) {
    if (points.length <= 2) {
        return points.length
    }
    let lines = Array.from({length: points.length}).map(_ => ({}));
    let sumLines = []
    while(points.length > 1) {
        let currentP = points.pop()
        let index = points.length
        points.forEach((p, i) => {
            let fixed = (currentP[0] - p[0]) / (currentP[1] - p[1])
            if (isNaN(fixed)) {
                fixed = 'nan'
            }
            let line = lines[index][fixed] || [index]
            if (line.indexOf(i) == -1) {
                line.push(i)
            }
            lines[index][fixed] = line
            lines[i][fixed] = line
            sumLines.push(line)
        })
    }
    return sumLines.sort((a, b) => a.length - b.length).pop().length
};

分析

忘了。以后再补