[LeetCode] 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 * (N - 1)条直线（如果含重复的点则直线数更少）。然后把直线表示成点斜式，根据斜率和截距进行来分组计数。试了下，发现这样要么得自己实现hashCode方法和equals方法，要么则要使用两层嵌套的HashMap。而且为了防止重复计数，必须得先将所有的点都放到一个set里，然后再看set的大小。实现的时间复杂度为O(N)。

发现一个更加简洁的方法是：还是使用两层循环，外层遍历所有点，让其成为起点，内层遍历所有除起始点之外的其它点，作为终点。这样一来，每一轮外层遍历，都会共享同一个起始点，这样的话判断直线是否相同只用判断斜率即可。关键是，每一次有一个新的起点的时候，都重建一个新的HashMap，可以轻松的避免了之前重复计数的可能。

这里需要有两个特殊点值得注意：

1）如果两个点在同一垂线上，斜率就设为无穷大；

2）如果两点重合，则要专门分开计数，因为这样的点可以在任意以其为起点的直线上。

	public int maxPoints(Point[] points) {
		if (points == null || points.length == 0)
			return 0;

		int maxCnt = 1;
		// select a starting point
		for (int i = 0; i < points.length; i++) {
			Map
  
    map = new HashMap
   
    (); int duplicateCnt = 0; // the # of duplicate points int localMaxCnt = 0; // the maximum count for a starting point // select an ending point for (int j = 0; j < points.length; j++) { if (i == j) continue; if (points[i].x == points[j].x && points[i].y == points[j].y) { duplicateCnt++; } else { double slope; if (points[i].x != points[j].x) { slope = (double) (points[i].y - points[j].y) / (points[i].x - points[j].x); } else { slope = Double.MAX_VALUE; } if (map.containsKey(slope)) { int count = map.get(slope) + 1; map.put(slope, count); localMaxCnt = Math.max(localMaxCnt, count); } else { map.put(slope, 1); localMaxCnt = Math.max(localMaxCnt, 1); } } } // add the # of duplicate points and itself localMaxCnt += duplicateCnt + 1; maxCnt = Math.max(localMaxCnt, maxCnt); } return maxCnt; }