149.Max-Points-on-a-Line

149. Max Points on a Line

题目地址

https://leetcode.com/problems/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.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

代码

Approach #1 Enumeration

Time O(N^2) Space O(N)

class Solution {
  int[][] points;
  int n;
  HashMap<Double, Integer> lines = new HashMap<Double, Integer>();
  int horizontal_lines;

  public int maxPoints(int[][] points) {
        this.points = points;
    n = points.length;
    if (n < 3)        return n;

    int max_count = 1;
    for (int i = 0; i < n - 1; i++) {
      max_count = Math.max(max_points_on_a_line_containing_point_i(i), max_count);
    }
    return max_count;
  }

  public int max_points_on_a_line_containing_point_i(int i) {
    lines.clear();
    horizontal_lines = 1;
    int count = 1;
    int duplicates = 0;

    for (int j = i + 1; j < n; j++) {
      Pair<Integer, Integer> p = add_line(i, j, count, duplicates);
      count = p.getKey();
      duplicates = p.getValue();
    }
    return count + duplicates;
  }

    public Pair<Integer, Integer> add_line(int i, int j, int count, int duplicates) {
    int x1 = points[i][0];
    int y1 = points[i][1];
    int x2 = points[j][0];
    int y2 = points[j][1];
    if (x1 == x2 && y1 == y2) {
      duplicates++;
    } else if (y1 == y2) {
      horizontal_lines += 1;
      count = Math.max(horizontal_lines, count);
    } else {
      double slope = 1.0 * (x1 - x2) / (y1 - y2) + 0.0;
      lines.put(slope, lines.getOrDefault(slope, 1) + 1);
      count = Math.max(lines.get(slope), count);
    }
    return new Pair(count, duplicates);
  }
}

#2

  /**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length <= 0) return 0;
        if(points.length <= 2) return points.length;
        int result = 0;
        for(int i = 0; i < points.length; i++){
            HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
            int samex = 1;
            int samep = 0;
            for(int j = 0; j < points.length; j++){
                if(j != i){
                    if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
                        samep++;
                    }
                    if(points[j].x == points[i].x){
                        samex++;
                        continue;
                    }
                    double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                    if(hm.containsKey(k)){
                        hm.put(k,hm.get(k) + 1);
                    }else{
                        hm.put(k, 2);
                    }
                    result = Math.max(result, hm.get(k) + samep);
                }
            }
            result = Math.max(result, samex);
        }
        return result;
    }
}