149. Max Points on a Line

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: Array、Hash Table、Math、Geometry

一、題目

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:
plane1

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

Example 2: plane2

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

Constraints:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • All the points are unique.

二、分析

  • 若干點在同一條線上，表示這些點的斜率都相同，注意題目有提示不會有相同的點，故兩點間必定有斜率。
    • 特別注意當分母為 0 時要特別處理。
    • 題目有限制 -10^4 <= xi, yi <= 10^4，故斜率最大 10^8，所以我們可以將分母為零的斜率暫定為 INT_MAX(2147483647)。
  • 遍歷每個點，並統計該點與其它點之間的斜率，將斜率用 unordered_map 記錄下來，其每個斜率的直線上總共會有 m+1 (加上自己)。

三、解題

1.

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)
int maxPoints(vector<vector<int>>& points) {
    int n = points.size();
    int res = 0;
    for (int i = 0; i < n; i++) {
        int& x0 = points[i][0];
        int& y0 = points[i][1];
        unordered_map<double,int> map;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;                   // 若等於自己則跳過
            int& x1 = points[j][0];
            int& y1 = points[j][1];
            if (x0 == x1) {                         // 當分母為 0 時特別處理
                int& cnt = ++map[INT_MAX];
                res = max(res, cnt);
            } else {
                double m = (y1-y0)/(1.0*(x1-x0));   // 注意將斜率轉成 double
                int& cnt = ++map[m];
                res = max(res, cnt);
            }
        }
    }
    return res + 1;                                 // 答案記得加 1，加上自己
}

回目錄 Catalog