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.

分析

暴力枚举法。两点决定一条直线，n个点两两组合，可以得到12n(n+1)\dfrac{1}{2}n(n+1)条直线，对每一条直线，判断n个点是否在该直线上，从而可以得到这条直线上的点的个数，选择最大的那条直线返回。复杂度O(n^3)。

上面的暴力枚举法以“边”为中心，再看另一种暴力枚举法，以每个“点”为中心，然后遍历剩余点，找到所有的斜率，如果斜率相同，那么一定共线对每个点，用一个哈希表，key为斜率，value为该直线上的点数，计算出哈希表后，取最大值，并更新全局最大值，最后就是结果。时间复杂度O(n^2)，空间复杂度O(n)。

以边为中心

  1. // Max Points on a Line
  2. // 暴力枚举法，以边为中心，时间复杂度O(n^3)，空间复杂度O(1)
  3. public class Solution {
  4.     public int maxPoints(Point[] points) {
  5.         if (points.length < 3) return points.length;
  6.         int result = 0;
  8.         for (int i = 0; i < points.length - 1; i++) {
  9.             for (int j = i + 1; j < points.length; j++) {
  10.                 int sign = 0;
  11.                 int a = 0, b = 0, c = 0;
  12.                 if (points[i].x == points[j].x) sign = 1;
  13.                 else {
  14.                     a = points[j].x - points[i].x;
  15.                     b = points[j].y - points[i].y;
  16.                     c = a * points[i].y - b * points[i].x;
  17.                 }
  18.                 int count = 0;
  19.                 for (int k = 0; k < points.length; k++) {
  20.                     if ((0 == sign && a * points[k].y == c +  b * points[k].x) ||
  21.                             (1 == sign&&points[k].x == points[j].x))
  22.                         count++;
  23.                 }
  24.                 if (count > result) result = count;
  25.             }
  26.         }
  27.         return result;
  28.     }
  29. }

以点为中心

  1. // Max Points on a Line
  2. // 暴力枚举，以点为中心，时间复杂度O(n^2)，空间复杂度O(n^2)
  3. public class Solution {
  4.     public int maxPoints(Point[] points) {
  5.         if (points.length < 3) return points.length;
  6.         int result = 0;
  8.         HashMap<Double, Integer> slope_count = new HashMap<>();
  9.         for (int i = 0; i < points.length-1; i++) {
  10.             slope_count.clear();
  11.             int samePointNum = 0; // 与i重合的点
  12.             int point_max = 1;    // 和i共线的最大点数
  14.             for (int j = i + 1; j < points.length; j++) {
  15.                 final double slope; // 斜率
  16.                 if (points[i].x == points[j].x) {
  17.                     slope = Double.POSITIVE_INFINITY;
  18.                     if (points[i].y == points[j].y) {
  19.                         ++ samePointNum;
  20.                         continue;
  21.                     }
  22.                 } else {
  23.                     if (points[i].y == points[j].y) {
  24.                         // 0.0 and -0.0 is the same
  25.                         slope = 0.0;
  26.                     } else {
  27.                         slope = 1.0 * (points[i].y - points[j].y) /
  28.                                 (points[i].x - points[j].x);
  29.                     }
  30.                 }
  32.                 int count = 0;
  33.                 if (slope_count.containsKey(slope)) {
  34.                     final int tmp = slope_count.get(slope);
  35.                     slope_count.put(slope, tmp + 1);
  36.                     count = tmp + 1;
  37.                 } else {
  38.                     count = 2;
  39.                     slope_count.put(slope, 2);
  40.                 }
  42.                 if (point_max < count) point_max = count;
  43.             }
  44.             result = Math.max(result, point_max + samePointNum);
  45.         }
  46.         return result;
  47.     }
  48. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/max-points-on-a-line.html