MENU

LeetCode149. Max Points on a Line(思维 / Hash)

2019 年 02 月 17 日 • 阅读: 1288 • LeetCode阅读设置

LeetCode149. Max Points on a Line(思维)

  • Hard
  • Accepted:111,618
  • Submissions:719,581

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

链接

https://leetcode.com/problems/max-points-on-a-line/

题意

给定平面上n个点,找到位于同一直线上的最大点数。

题解

  • 暴力解法,两层循环遍历点组成一条直线,然后再一层循环求剩余所有点到该直线的距离,判断点是否落在直线上,时间复杂度$O(n^3)$,爆炸。
  • 如何确定一条直线?除了两点之外,还可以用点和斜率确定一条直线,所以如果两个点A、B与某个点C构成的直线的斜率一样,那么A、B、C三点共线。
  • 因此我们可以一层循环遍历所有的点,然后求其余点与该点连线的斜率,将所有斜率相同的使用查找表unordered_map保存,答案就是表中的最大值加上原来的那点。时间复杂度$O(n^2)$。
  • 可能出现的问题:

    • 如果两个点相同,那么需要单独处理,加上重复的点,求的时候只用其中一个点。
    • 如果直线的斜率不存在,那么可以单独设一个值,如INT_MAX。
  • 斜率存在精度问题,无法避免,会被部分数据卡死,比如[[0,0],[94911151,94911150],[94911152,94911151]],所以还是得改一下。(有人说long double可以解决这个问题)
  • 我们可以不存储浮点数形式的斜率,而是用化简后的分数$\frac{y}{x}​$来表示斜率,这样就避免了浮点误差。但是unordered_map没法把pair对作为键值,所以我们得改用map来存储。这样的话时间复杂度为$O(n^2logn)​$。
  • 如果我们用unordered_map来存pair的话得自己写hash函数,否则无法通过编译,比较麻烦。
  • 还有一种使用unordered_map的方法,我们可以把化简后的分数$\frac{y}{x}​$转成字符串x+' '+y​而不使用pair。

代码

  • Runtime: 16 ms, faster than 100.00% of C++ online submissions for Max Points on a Line.
  • Memory Usage: 10.3 MB, less than 100.00% of C++ online submissions for Max Points on a Line.
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int n = points.size();
        int duplicate; // 相同点数量
        int ans = 0;
        int slopex, slopey, slopegcd; // 斜率分数形式
        map<pair<int, int>, int> umap; // 斜率-次数
        for (int i = 0; i < n; ++i)
        {
            duplicate = 1; // 初始化为1即点i
            for (int j = i + 1; j < n; ++j)
            {
                if (points[j].x == points[i].x && points[j].y == points[i].y) // 相同点只需计算一个
                {
                    ++duplicate;
                    continue;
                }
                slopex = (points[j].x - points[i].x);
                slopey = (points[j].y - points[i].y);
                slopegcd = __gcd(slopex, slopey); // 最大公因数
                umap[make_pair(slopex / slopegcd, slopey/ slopegcd)]++;
            }
            ans = max(ans, duplicate);
            for (auto it : umap) // 找到最大的
                ans = max(ans, it.second + duplicate);
            umap.clear();
        }
        return ans;
    }
};
  • Wrong Answer,斜率做法
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int n = points.size();
        int duplicate; // 相同点数量
        int ans = 0;
        double slope; // 斜率
        unordered_map<double, int> umap; // 斜率-次数 
        for (int i = 0; i < n; ++i)
        {
            duplicate = 1; // 初始化为1即点i
            for (int j = i + 1; j < n; ++j)
            {
                if (points[j].x == points[i].x && points[j].y == points[i].y) // 相同点只需计算一个
                {
                    ++duplicate;
                    continue;
                }
                if (points[j].x == points[i].x) // 斜率不存在
                    slope = INT_MAX * 1.0;
                else
                    slope = (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x);
                umap[slope]++;
            }
            ans = max(ans, duplicate);
            for (auto it : umap) // 找到最大的
                ans = max(ans, it.second + duplicate);
            umap.clear();
        }
        return ans;
    }
};

参考


The end.
2019年2月17日 星期日
最后编辑于: 2019 年 03 月 04 日