P185 位于同一直线的最多点数

描述#

这个题目说的是，给你二维平面上 n 个点，你要计算出最多有多少个点可以位于同一条直接上。

注意，给你的 n 个点中，可能包含相同的点。

比如说，给你的点是：
[[0,0], [0,0], [0,1], [1,1], [2,2]]
两个 [0,0] 和 [1,1]、[2,2] 这 4 个点都位于 y = x 这条直线上。并且不存在其他直线，可以包含更多的点。因此位于同一直线上最多的点数就为 4。

代码#

public class AlgoCasts {

  // Time: O(n^3), Space: O(1)
  public int maxPointsBruteForce(int[][] points) {
    if (points == null || points.length == 0) return 0;
    int max = 1;
    for (int i = 0; i < points.length; ++i) {
      long ax = points[i][0], ay = points[i][1];
      int samep = 0;
      for (int j = i+1; j < points.length; ++j) {
        long bx = points[j][0], by = points[j][1];
        if (ax == bx && ay == by) {
          ++samep;
          continue;
        }
        int cur = 2;
        for (int k = j+1; k < points.length; ++k) {
          long cx = points[k][0], cy = points[k][1];
          if ((by-ay) * (cx-ax) - (bx-ax) * (cy-ay) == 0)
            ++cur;
        }
        max = Math.max(max, cur + samep);
      }
      max = Math.max(max, samep + 1);
    }
    return max;
  }

  private long gcd(long x, long y) {
    return y == 0 ? x : gcd(y, x % y);
  }

  // Time: O(n^2), Space: O(n)
  public int maxPointsHashMap(int[][] points) {
    if (points == null || points.length == 0) return 0;
    int max = 1;
    for (int i = 0; i < points.length; ++i) {
      Map<Long, Integer> map = new HashMap<>();
      long ax = points[i][0], ay = points[i][1];
      int samep = 0;
      int lineMax = 0;
      for (int j = i+1; j < points.length; ++j) {
        long bx = points[j][0], by = points[j][1];
        long x = bx - ax, y = by - ay;
        if (x == 0 && y == 0) {
          ++samep;
          continue;
        }
        long g = gcd(x, y);
        x /= g;
        y /= g;
        long key = (x << 32) + y;
        int count = map.getOrDefault(key, 0);
        ++count;
        map.put(key, count);
        lineMax = Math.max(lineMax, count);
      }
      max = Math.max(max, lineMax + samep + 1);
    }
    return max;
  }

}