LeetCode 149. Max Points on a Line [Hard] [C++] 解題筆記

 Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

 

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

想法:

    這題給我們一堆點的座標，要我們求出由這些點組成的直線中哪一條包含的點最多。這題簡單來說就是我們需要列舉

每兩點之間組成的直線然後判斷線上有幾點，兩點是否共線可以利用線的斜率來判斷，最後要記得考慮座標相同的點。

這題想法不難但實作細節蠻多需要多注意的。

完整程式碼:

/* O(n^2)
 * corner case: vertical/horizontal line 
 */
class Solution {
public:
    typedef pair<int, int> Point;
    int maxPoints(vector<vector<int>>& points) {
        const int n = points.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // slope: dx, dy, count
            // can not use unordered_map, pair is un-hashable
            // 一定要寫在裡面避免重複計算，ex: (0,0) (1,1) (2,2).
            map<Point, int> count;
            int same_points = 1;
            int max_points = 0;
            const Point& p1 = make_pair(points[i][0], points[i][1]);
            for (int j = i + 1; j < n; j++) {
                const Point& p2 = make_pair(points[j][0], points[j][1]);
                if (p1.first == p2.first && p1.second == p2.second) {
                    ++same_points;
                }
                else {
                    max_points = max(max_points, ++count[getSlope(p1, p2)]);
                }
            }
            ans = max(ans, same_points + max_points);
        }
        return ans;   
    }
    Point getSlope(const Point& p1, const Point& p2) {
        const int dx = p2.first - p1.first;
        const int dy = p2.second - p1.second;
        // vertical line
        if (dx == 0) { return make_pair(p1.first, 0); }
        if (dy == 0) { return make_pair(0, p1.second); }
        int d = gcd(dx, dy);
        return make_pair(dx / d, dy / d);
    }
    int gcd(int m, int n) {
        return (n == 0)? m : gcd(n, m % n);
    }
};