幾何應用: 最多有幾個點共線? Max Points on a Line_Leetcode #149

Ian Taylor on Unsplash

題目敘述 149. Max Points on a Line

給定一串2維平面的點座標，請問最多有幾個點落在同一條直線上?

測試範例

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

約束條件

Constraints:

• 1 <= points.length <= 300

做少一個給一個點座標，最多給300個點座標。

• points[i].length == 2

點座標落在xy平面上，第一個欄位是x座標，第二個欄位是y座標。

• -10^4 <= xi, yi <= 10^4

x座標, y座標都落在正負一萬以內的區間。

• All the points are unique.

所有的點座標都不重複。

觀察

任意兩點必共線。(因為任意不同的兩點肯定構成一條直線)

若要更多點的共線，則必須彼此的斜率都相同!

演算法 計算有多少組斜率相同的連線

如果一群點座標共線，那麼他們倆兩之間的斜率一定都相同。

建立一個字典，掃描過每個兩兩一組點座標，統計斜率相同的次數。

斜率相同次數最多的那組，就是擁有最多點座標共線，

最後返回共線的點座標數量即可。

程式碼 計算有多少組斜率相同的連線

class Solution:

    # member method to compute greatest common factor
    def gcd(self, x, y):
        if y == 0 :
            return x
        else:
            return self.gcd( y, x % y )

    def maxPoints(self, points: List[List[int]]) -> int:
        
        # total number of 2D points
        size = len( points )

        # to sotre the maximum number of colonear 2D points
        max_num_of_points_colinear = 0

        for i in range( size ):
            
            ## Dictionary:
            # key: (x_delta, y_delta)
            # vluae: number of colinear pointer with slope = y_delta / x_delta
            on_the_same_line = defaultdict( int )

            repeated_2D_point = 1

            # get coordinate of 2D Point i
            x_of_point_i = points[i][0]
            y_of_point_i = points[i][1]

            for j in range(i+1, size):

                # get coordinate of 2D Point j
                x_of_point_j = points[j][0]
                y_of_point_j = points[j][1]

                delta_x = x_of_point_i - x_of_point_j
                delta_y = y_of_point_i - y_of_point_j   
                
                # get greatest common factor
                factor = self.gcd( delta_x, delta_y )                

                # simplify to irreducible fraction
                delta_x /= factor
                delta_y /= factor

                # update the number of colinear 2D point
                #
                on_the_same_line[(delta_x, delta_y)] += 1

							#----------------------------------------------------
            current_max_num_pt_colinear = 1

            # get the max number of colinear points
            if len( on_the_same_line ) != 0:
                current_max_num_pt_colinear = max( on_the_same_line.values() ) + 1

            # update the global max number of colinear points
            max_num_of_points_colinear = max( max_num_of_points_colinear, current_max_num_pt_colinear)
    
        return max_num_of_points_colinear

複雜度分析

時間複雜度: O(n^2)

總共有C(n, 2)個點座標pair，掃描這些點座標pair，計算斜率，統計斜率的相同次數。

空間複雜度: O(n)

需要建立一個字典去儲存斜率。

最差情況下，每個pair的斜率都不相同。

Reference

[1] Max Points on a Line - LeetCode