正文
LeetCode-Max Points on a Line[AC源码]
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
package com.lw.leet3; import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry; /**
* @ClassName:Solution
* @Description: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.
* @Author LiuWei
* @Date 2014年8月17日下午2:51:08
* @Mail nashiyue1314@163.com
*/ /**
* 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) {
int max = 0;
if(points.length <= 2){
max = points.length;
}
else{
for(int i = 0; i < points.length; i++){
int equalNum = 0;
Map<Double, Integer> map = new HashMap<Double, Integer>();
for(int j = i+1; j < points.length; j++ ){
if(points[i].x == points[j].x && points[i].y == points[j].y){
equalNum ++;
continue;
} double k = 0;
if(points[i].x == points[j].x){
k = Double.MAX_VALUE;
}
else{
k = ((double)(points[i].y - points[j].y)/(points[i].x - points[j].x));
/**
* Submission Result: Wrong Answer
* Input: [(2,3),(3,3),(-5,3)]
* Output: 2
* Expected:3
*
* avoid k = +0.0 -0.0
* */
if(k == 0){
k = 0;
}
} if(map.containsKey(k)){
map.put(k, map.get(k)+1);
}
else{
map.put(k, 2);
}
} /**
* Submission Result: Wrong Answer
* Input: [(1,1),(1,1),(1,1)]
* Output: 0
* Expected:3
*
* avoid the points are all equal
* */
if(equalNum > max){
max = equalNum + 1 ;
}
Iterator<Entry<Double, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()){
Entry<Double, Integer> entry = iter.next();
int num = entry.getValue();
if( num + equalNum > max){
max = num + equalNum;
}
}
}
}
return max;
} public static void main(String[] args){
Point[] p = {new Point(2, 3),new Point(3,3),new Point(-5,3)};
// Point[] p = {new Point(1, 1),new Point(1,1),new Point(1,1)}; Solution s = new Solution();
System.out.println(s.maxPoints(p)); } }
