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.

题目链接

算法分析

拿到这题可能一开始无从下手。我也是这样！

枚举每个点，假设所有的直线必须通过这个点。计算该点与其他所有点之间的斜率，并使用HashMap存储。如果斜率相同，那么这些点必然在一条直线上（一点和斜率确定一条直线）。 同时，还要考虑重合的点、斜率不存在的情况。

另外，参考代码中还涉及到自定义pair的hash函数。可以参考这里。 因为unordered_map没有为pair定义hash函数。

• 时间复杂度：O(n^2)
• 空间复杂度: O(n)
• n 是点的个数

参考代码

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */

typedef pair<int, int> pii;

struct pairhash {
    template<class T, class U>
    size_t operator() (const pair<T, U> &p) const {
        return hash<T>()(p.first) ^ hash<U>()(p.second);
    }
};

class Solution {
public:
    /**
     * @param points an array of point
     * @return an integer
     */
    int maxPoints(vector<Point>& points) {
        // Write your code here
        int n = points.size();
        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            unordered_map<pii, int, pairhash> cnt;
            // coincide 记录与该点重合的点的个数
            // verticle 记录与该点相连斜率不存在的点的个数
            int coincide = 0, verticle = 0;
            for (int j = 0; j < n; ++ j) {
                if (points[j].x == points[i].x && points[j].y == points[j].y) {
                    ++ coincide;
                } else if (points[j].x == points[i].x) {
                    ++ verticle;
                } else {
                    int x = points[j].x - points[i].x;
                    int y = points[j].y - points[i].y;
                    int g = gcd(x, y);
                    if (g != 0) {
                        x /= g, y /= g;
                    }
                    ++ cnt[pii(y, x)];
                }
            }

            ans = max(ans, coincide);
            ans = max(ans, verticle);
            for (auto &p: cnt) {
                ans = max(ans, p.second + 1);
            }
        }
        return ans;
    }

    int gcd(int a, int b) {
        if (!b) return a;
        return gcd(b, a % b);
    }
};