Max Points on a Line

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

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

Thoughts

给一堆以二维坐标表示的点，问它们构成的直线中最多能有多少个点在线上。以i点为基准点，算其它点和它构成的斜率，当斜率相同说明这些点都在同一条直线。因此用map统计存在过的斜率和对应出现的次数。有两个特别的corner case需要注意: 1. 重复的点 2. 由于精度有限, 不能直接存斜率. 而是存y_diff和x_diff分别对gcd(y_diff, x_diff)的倍数。

Code

/*
 * @lc app=leetcode id=149 lang=cpp
 *
 * [149] Max Points on a Line
 */
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        const int N = points.size();
        std::function<int(int, int)> gcd;
        gcd = [&gcd](int a, int b)->int {
            if (b == 0) return a;
            return gcd(b, a % b);
        };
        int res = 0;
        unordered_map<string, int> freq;
        for (int i = 0; i < N; ++i) {
            const auto &p1 = points[i];
            freq.clear();
            int dup = 1;
            int local_max = 0;
            for (int j = i + 1; j < N; ++j) {
                const auto &p2 = points[j];
                if (p1[0] == p2[0] && p1[1] == p2[1]) {
                    ++dup;
                    continue;
                }
                const int y_diff = p1[1] - p2[1], x_diff = p1[0] - p2[0];
                const int g = gcd(y_diff, x_diff);
                const auto key = to_string(y_diff / g) + "," + to_string(x_diff / g);
                if (!freq.count(key)) freq[key] = 0;
                ++freq[key];
                local_max = max(local_max, freq[key]);
            }
            res = max(res, local_max + dup);
        }
        return res;
    }
};

Analysis

时间复杂度O(N ^ 2), 空间O(N).