LeetCode - 149.Max Points on a Line

tags: LeetCode Guide C++ Hard

原題連結: https://leetcode.com/problems/max-points-on-a-line/

Difficulty: Hard

題目說明

原文

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

翻譯

給定n個2D平面上的點，找出所有可能的共線中，含有點最多的點個數。

範例測資

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

Note

input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Code與解析

作法1. Brute Force [TimeLimitExceed]

基本上一定會超時，所以我就不做了。
簡單來說就是分別找2個點，然後把其他點全部檢查一次，時間複雜度會是O(n^3)

作法2. Optimal Solution [Accept]

Runtime: 12 ms > 98.24%
Memory: 9.2 MB > 78.57%

class Solution {
   public:
    int maxPoints(vector<vector<int>>& points) {
        // If points' amount equal or less than 2, answer is points' amount.
        if (points.size() <= 2) return points.size();

        map<double, int> slopes;  // Saving the counts in same slope.
        int res = 2;
        while (points.size() > 2) {
            int vertical = 1;
            // Choose the last point in the list.
            int x = points[points.size() - 1][0];
            int y = points[points.size() - 1][1];
            slopes.clear();
            int tempRst = 0;
            int overlapped = 0;
            // Check with every other point.
            for (int i = points.size() - 2; i >= 0; i--) {
                if (points[i][0] == x && points[i][1] != y)
                    ++vertical;                                     // Check point on vertical line.
                else if (points[i][0] == x && points[i][1] == y) {  // Check overlapped point.
                    ++overlapped;
                    points.erase(points.begin() + i);  // It's the same point, so we just need to check it once, skip it anyway.
                } else
                    ++slopes[((double)(points[i][1] - y) / (points[i][0] - x))];
            }
            for (auto& i : slopes)
                if (++i.second > tempRst) tempRst = i.second;                    // Find the maximum result of this point.
            tempRst = ((tempRst > vertical) ? tempRst : vertical) + overlapped;  // Same as above.
            res = max(res, tempRst);                                             // Is this the most result so far?
            points.pop_back();                                                   // This point already checked, so skip it anyway.
        }
        return res;
    }
};

這個做法很像暴力破解，但是用了一點技巧。
首先，每次的迭代只找一個點，並且輪流跟其他點計算斜率。(程式碼Line18~26的部分。)
這樣一來，我可以確定把選定的這個點相關的所有線都找完。
並且，從3點共線的定義：

1. 此線通過選定點。
2. 共線的點之間互連的直線斜率必定相同。

可以反推回去。
又因為一次迭代就會把關於這個選定點的直線檢查完，所以在計算後可以先刪除。
之後每次迭代就只需要檢查剩餘的點即可。