Simple way to solve precision problem in([0, 0], [94911151, 94911150], [94911152, 94911151])


  • 0
    Z

    Due the division of double type has only 16 decimals, the last test case will fail. A simple to solve these problem is to times a larger value such as 10000000000000.0.

    This is my accepted java code in O(n^2) using HashMap

    public class Solution {
        public int maxPoints(Point[] points) {
        	int res = 0;
        	HashMap<Double, Integer> map = new HashMap<Double, Integer>();
        	for(int i = 0; i < points.length; i++) {
        		map.clear();
        		Point p1 = points[i];
        		int duplicate = 1;
        		for(int j = 0; j < points.length; j++) {
        			Point p2 = points[j];
        			if(j == i) continue;
        			if(p1.x == p2.x && p1.y == p2.y) {
        				duplicate++;
        				continue;
        			}
        			if(p1.x == p2.x) {
        				if(map.get((double)Integer.MAX_VALUE) != null) {
        					map.put((double)Integer.MAX_VALUE, map.get((double)Integer.MAX_VALUE) + 1);
        				}
        				else map.put((double)Integer.MAX_VALUE, 1);
        				continue;
        			}
        			Double k = 10000000000000.0 * (double)(p2.y - p1.y) / (double)	(p2.x - p1.x);
        			if(map.get(k) != null) {
        				map.put(k, map.get(k) + 1);
        			}
        			else map.put(k, 1);
        		}
        		int max = duplicate;
        		for(Double key : map.keySet()) {
        			if(map.get(key) + duplicate > max) max = map.get(key) + duplicate;
        		}
        		if(max > res) res = max;
        	}
        	return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.