2014年4月29日 星期二

[LeetCode] Max Points on a Line

Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:O(n*n)
public class Solution {
   public int maxPoints(Point[] points) {
      Map<Double, Integer> map = new HashMap<>();
      int ret = 0;
      int size = points.length;
      for (int i = 0; i < size; i++) {
         int invalidK = 0;
         int add = 1;
         for (int j = i + 1; j < size; j++) {
            if (points[j].x == points[i].x) {
               if (points[j].y == points[i].y) {
                  add++;
               } else {
                  invalidK++;
               }
               continue;
            }
            double slope = points[j].y == points[i].y ? 0.0: (1.0 * (points[j].y - points[i].y))/ (points[j].x - points[i].x);
     if (map.containsKey(slope)) {
               int count = map.get(slope);
        map.put(slope, count + 1);
     } else {
        map.put(slope, 1);
     }
         }
         for (Integer it : map.values()) {
            ret = Math.max(it.intValue() + add, ret);
         }
         ret = Math.max(invalidK + add, ret);
         map.clear();
      }
      return ret;
   }
}

沒有留言:

張貼留言