首页 > 基础算法 > 模拟法 > LeetCode-Max Points on a Line[模拟]
2014
11-19

LeetCode-Max Points on a Line[模拟]

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.

标签: Hash Table Math
分析

暴力枚举法。两点决定一条直线,$n$个点两两组合,可以得到$\dfrac{1}{2}n(n+1)$条直线,对每一条直线,判断$n$个点是否在该直线上,从而可以得到这条直线上的点的个数,选择最大的那条直线返回。复杂度$O(n^3)$。

上面的暴力枚举法以“边”为中心,再看另一种暴力枚举法,以每个“点”为中心,然后遍历剩余点,找到所有的斜率,如果斜率相同,那么一定共线对每个点,用一个哈希表,key为斜率,value为该直线上的点数,计算出哈希表后,取最大值,并更新全局最大值,最后就是结果。时间复杂度$O(n^2)$,空间复杂度$O(n)$。

代码1

// LeetCode, Max Points on a Line
// 暴力枚举法,以边为中心,时间复杂度O(n^3),空间复杂度O(1)
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        if (points.size() < 3) return points.size();
        int result = 0;

        for (int i = 0; i < points.size() - 1; i++) {
            for (int j = i + 1; j < points.size(); j++) {
                int sign = 0;
                int a, b, c;
                if (points[i].x == points[j].x) sign = 1;
                else {
                    a = points[j].x - points[i].x;
                    b = points[j].y - points[i].y;
                    c = a * points[i].y - b * points[i].x;
                }
                int count = 0;
                for (int k = 0; k < points.size(); k++) {
                    if ((0 == sign && a * points[k].y == c +  b * points[k].x) || 
                        (1 == sign&&points[k].x == points[j].x)) 
                        count++;
                }
                if (count > result) result = count;
            }
        }
        return result;
    }
};

代码2

// LeetCode, Max Points on a Line
// 暴力枚举,以点为中心,时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        if (points.size() < 3) return points.size();
        int result = 0;

        unordered_map<double, int> slope_count;
        for (int i = 0; i < points.size()-1; i++) {
            slope_count.clear();
            int samePointNum = 0; // 与i重合的点
            int point_max = 1;    // 和i共线的最大点数

            for (int j = i + 1; j < points.size(); j++) {
                double slope; // 斜率
                if (points[i].x == points[j].x) {
                    slope = std::numeric_limits<double>::infinity();
                    if (points[i].y == points[j].y) {
                        ++ samePointNum;
                        continue;
                    }
                } else {
                    slope = 1.0 * (points[i].y - points[j].y) / 
                        (points[i].x - points[j].x);
                }

                int count = 0;
                if (slope_count.find(slope) != slope_count.end())
                    count = ++slope_count[slope];
                else {
                    count = 2;
                    slope_count[slope] = 2;
                }

                if (point_max < count) point_max = count;
            }
            result = max(result, point_max + samePointNum);
        }
        return result;
    }
};

Java代码:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
 import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
public class Solution {
  public static int maxPoints(Point[] points) {
		if(points.length == 0) return 0;
		HashMap<Double,Integer> map = new HashMap<Double,Integer>();
		int ans = 1;
		for (int i = 0; i < points.length; i++) {
			map.clear();
			int tmp = 1;
			int de = 0;
			for (int j = 0; j < points.length; j++) {
				if(j == i) continue;
				if(points[i].x == points[j].x && points[i].y == points[j].y){
				       de++; 
				        continue;      
				}
				double d = d(points[i], points[j]);
				Integer cnt = map.get(d);
				if(cnt == null)
					map.put(d, 2);
				else map.put(d, cnt+1);
			}
			Set<Entry<Double, Integer>> entrySet =  map.entrySet();
			for(Entry<Double, Integer> e:entrySet){
				if(tmp <e.getValue())
					tmp = e.getValue();
			}
			if(ans < tmp+de) ans = tmp+de;
		}
		
		return ans;
	}
	
	static double d(Point p1,Point p2){
	    if((p1.y-p2.y) == (p1.x-p2.x)) return 1;
		return (p1.y-p2.y)*1.0/(p1.x-p2.x);
	}
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。