直线上最多的点数

[louzhedong]

习题

出处 LeetCode 算法第149题

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

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

思路

这题的关键是会有重复的点，所以在最开始可以将重复的点过滤掉，并通过一个map来保存每个坐标的点的个数，通过公式 (y3-y2)*(x2-x1)==(y2-y1)*(x3-x2)来判断三个点是否在同一直线上，最外层只能使用穷举法。

解答

function Point(x, y) {
  this.x = x;
  this.y = y;
}
/**
 * @param {Point[]} points
 * @return {number}
 */
var maxPoints = function (points) {
  var length = points.length;
  if (length <= 2) return length;
  var diffMap = {};
  var setPoints = [];
  points.forEach(item => {
    var key = item.x + ',' + item.y;
    if (key in diffMap) {
      diffMap[key]++;
      delete item;
    } else {
      diffMap[key] = 1;
      setPoints.push(item);
    }
  })
  var size = setPoints.length;
  if (size == 1) {
    return diffMap[setPoints[0].x + ',' + setPoints[0].y];
  }
  if (size == 2) {
    return diffMap[setPoints[0].x + ',' + setPoints[0].y] + diffMap[setPoints[1].x + ',' + setPoints[1].y];;
  }
  var max = 0;
  for (var i = 0; i < size; i++) {
    for (var j = i + 1; j < size; j++) {
      var point1 = setPoints[i];
      var point2 = setPoints[j];
      var key1 = point1.x + ',' + point1.y;
      var key2 = point2.x + ',' + point2.y;
      var temp = diffMap[key1] + diffMap[key2];
      for (var k = j + 1; k < size; k++) {
        var point3 = setPoints[k];
        if (((Number(point3.y) - Number(point2.y)) * (Number(point2.x) - Number(point1.x))) == ((Number(point2.y) - Number(point1.y)) * (Number(point3.x) - Number(point2.x)))) {
          temp += diffMap[point3.x + ',' + point3.y];
        }
      }
      if (temp > max) {
        max = temp;
      }
    }
  }

  return max;
};


console.log(maxPoints([new Point(3, 1), new Point(12, 3), new Point(3, 1), new Point(-6, -1)]))