149. Max Points on a Line

leetcode 
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();

        // 保存經過相同直線的最多點的數量
        int maxSlope = 0;

        // 保存斜率與點個數的 mapping
        // {斜率: 通過的點個數}
        unordered_map<double, int> m;

        // 使用兩個迴圈走訪兩個 points
        for (int i = 0 ; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // point1(x1, y1)
                double x1 = points[j][0];
                double y1 = points[j][1];

                // point2(x2, y2)
                double x2 = points[i][0];
                double y2 = points[i][1];

                if(y2 == y1 && x2 == x1)
                {
                    // 如果兩個點重疊，則跳過這個點
                    continue;
                }
                else if (x2 == x1)
                {
                    // 如果兩個點在 x 軸上重合
                    // 斜率為 INT_MAX
                    m[INT_MAX]++;
                }
                else
                {
                    // 其他的狀況才可以套用斜率公式
                    double slope = (y2 - y1) / (x2 - x1);
                    // 對於相同的斜率，點的個數 + 1
                    m[slope]++;
                }
            }

            // 對於每個點，走訪 m 並找到最多點的斜率，並將其保存到 curMax 中。
            int curMax = 0;
            for (auto a : m)
            {
                curMax = max(curMax, a.second);
            }
            maxSlope = max(maxSlope, curMax);

            // 清空 hashMap，計算下一次的組合
            m.clear();
        }
        // 最後回傳 maxSlope + 1，因為需要考慮到自己本身
        return maxSlope + 1;
    }
};
  • T: O(N2)O(N^2)
  • S: O(N)O(N)