Skip to main content

149. Max Points on a Line

直線的公式：y = ax + b 特殊情況：

  • 兩個點重疊的情況。
  • 兩個點在 x 軸上重合的狀況，如果 (x2−x1)(x_2 - x_1) 為 0，則沒辦法計算斜率。

對於兩個點 (x1,y1)(x_1, y_1) 和 (x2,y2)(x_2, y_2) 計算斜率 k 的公式：k=(y2−y1)/(x2−x1)k = (y_2 - y_1) / (x_2 - x_1)

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)