LeetCode149. Max Points on a Line（思维 / Hash）

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;
    }
};

参考

• 16ms/28ms C++ Solutions with Explanations

• unordered_map with pair as key - not compiling

The end.
2019年2月17日 星期日