欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

max-points-on-a-line(最多有多少个点位于同一条直线上)

程序员文章站 2022-04-01 17:56:06
...

原题链接

问题一:如何确定点在同一个直线上? 可以选定一个点,然后根据其他的点到这个点的斜率来判断在同一直线上的点的数目。
问题二:如果点和选定的点是垂直的关系怎么办??就是不能直接求斜率了,因为分母为0, 那就直接用一个变量记录就好啦。
问题三:如果点和选定的点是重复的怎么办??也是把重复的点记录下来,到时候返回最终结果的时候加上重复的点的个数就好了。

思路:遍历每个点,即定一个点, 用map容器记录该点与其他点的斜率,并统计该斜率的次数(相当于记录有多少个点位于同一条直线上)

对于和选定的点垂直的点(即斜率不存在) 和 重合的点要分开记录。


class Solution {
public:
	

    int maxPoints(vector<Point> &points) {
		int n = points.size();
		if(n <= 0)
			return 0;
		int res = 0;
		for(int i = 0; i < n; i++){
			map<double, int>m;//键记录斜率,值记录在同一条直线的点的个数
			int vertical = 0;//因和points[i]垂直而在同一条直线的点的个数
			int dup = 0;//和points[i]重复的点的个数
			int curMax = 1;//当前最大的在同一条直线的点的个数
			for(int j = 0; j < n; j++){//选定一个点
				if(j != i){
					double x = points[i].x - points[j].x;
					double y =  points[i].y - points[j].y;
					if(x == 0 && y == 0){//点重合
						dup++;

					}
					else if(x == 0){//点垂直定点
						if(vertical == 0)
							vertical = 2;
						else
							vertical++;
					}
					else{
						double k = y / x;
						if(m[k] == 0)
							m[k] = 2;
						else
							m[k]++;//斜率为K的点的个数增加,即同一条直线的点个数相加
					}
						
				}


			}
			//求最大的在同一条直线的上的点的个数(不包括重复的点)
			curMax = max(curMax, vertical);
			for(map<double, int>::iterator it = m.begin(); it != m.end(); it++){
				if(it->second > curMax)
					curMax = it->second;
			}
			
			//记得加上重复的点才是最终的在同一条直线上的点的数目
			res = max(res, curMax + dup) ;
			
		}

		return res;
    }

	
};

JAVA版本:

在这里插入代码片
package Leetcode;

import java.util.HashMap;
import java.util.Iterator;

class Point {
      int x;
      int y;
      Point() { x = 0; y = 0; }
      Point(int a, int b) { x = a; y = b; }
}
 

public class Solution {
    public static int maxPoints(Point[] points) {
    	if(points == null)
    		return 0;
        int n = points.length;
        if(n <= 0)
        	return 0;
        
        int res = 0;
        for(int i = 0; i < n; i++) {
        	
        	HashMap<Double, Integer> m = new HashMap<>();
        	int curMax = 1;
        	int dup = 0;
        	int ver = 0;
        	for(int j = 0; j < n; j++) {
        		if(j != i) {
        			double x = points[i].x - points[j].x;
        			double y = points[i].y - points[j].y;
        			if(x == 0 && y == 0)
        				dup++;
        			else if(x == 0) {
        				if(ver == 0)
        					ver = 2;
        				else
        					ver++;
        			}
        			else {
        				double k = y / x;
        				//m.containKey(key)判断key是否存在map容器
        				//利用m.put加入容器
        				//m.get来获取容器的value 
        				if(m.containsKey(k) == false) {
        					m.put(k, 2);
        				}
        				else {
        					
        					m.put(k, m.get(k) + 1);
        					
        				}
        					
        					
        			}
        		}
        	}
        	
        	curMax = Math.max(curMax, ver);
        	//利用迭代器访问map容器
        	Iterator<Double> iterator = m.keySet().iterator();
        	while(iterator.hasNext()) {
        		double  key = iterator.next();
        		int tmp = m.get(key);
        		
        		if(tmp > curMax)
        			curMax = tmp;
        		
        	}
        	
        	res = Math.max(res, curMax + dup);
        	
        }
    	return res;
    }
    
    
    public static void main(String args[]) {
    	Point a = new Point(2, 3);
    	Point b = new Point(3, 3);
    	Point c = new Point(-5, 3);
    	Point[] points = new Point[3];
		points[0] = a;
    	points[1] = b;
    	points[2] = c;
    	int res = maxPoints(points);
    	System.out.println(res);
    }
}