当前位置：首页 > news >正文

LeetCode -- Max Points on a Line

news 来源：原创 2024/5/10 5:58:44

题目描述：

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

思路：
这算是一道数学题，关键在于存方程，把点一一代入判断是否满足。

1. 两层循环遍历节点O，存直线方程的关键因子：斜率：K, 截距：B，X：X轴截距（K为无穷时），Y:Y轴截距（K为0时）。
2. 对每个方程分别遍历每个点，找到满足最多点的方程即可。

注：在小于精度0.00001时，本解法有Bug

实现代码：


 /**
 * Definition for a point.
 * public class Point {
 *     public int x;
 *     public int y;
 *     public Point() { x = 0; y = 0; }
 *     public 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 1;
    	}
     	
    	// 1. same line functions into list
    	var funcs = new Dictionary<string, LineFunc>();
    	
    	for(var i = 0;i < points.Length; i++){
    		for(var j = 0; j < points.Length;j ++){
    			if(i != j){
    				var line = Line(points[i], points[j]);
    				var k = line.ToString();
    				if(!funcs.ContainsKey(k)){
    					funcs.Add(k,line);
    				}
    			}
    		}
    	}


    	// 2. loop each function , count how many points can fulfil
    	var max = 0;
    	foreach(var k in funcs.Keys){
    		var c = 0;
    		for(var i = 0;i < points.Length; i++){
    			if(funcs[k].Test(points[i])){
    				c++;
    			}
    		}
    		if(c > max){
    			max = c;
    		}
    	}
    	
    	return max;
    }


private LineFunc Line(Point p1 , Point p2){
	double deltaX = p1.x - p2.x;
	var k = deltaX == 0 ? int.MaxValue : ((p1.y - p2.y) / deltaX);
	var b = p1.y - k * p1.x;
	
	return new LineFunc(k,b,p1.x,p1.y);
}


public class LineFunc{


	public LineFunc(double k , double b, double x0, double y0){
		K = k;
		if(k == 0){
			Y = y0;
		}
		else if(k == int.MaxValue){
			X = x0;
		}
		else{
			B = b;
		}
	}
	
	public bool Test(Point p){
		if(K == int.MaxValue){
			return p.x == X;
		}
		else if(K == 0){
			return p.y == Y;
		}
		else{
			var delta = p.y - (p.x * K + B);
			return delta < 0.00001 && delta > -0.000001;
		}
	}
	
	public double K;
	public double Y;
	public double X;
	public double B;
	
	public override string ToString(){
		return string.Format("{0}_{1}_{2}_{3}", K, B, X, Y);
	}
}




}