Source: InterviewBit – Points on the Straight Line

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

Sample Input :

(1, 1)
(2, 2)

Sample Output :

2

You will be given 2 arrays X and Y. Each point is represented by (X[i], Y[i])

解題：

  1. 從 2D 座標系的概念可以得知，要確認各點是否在同一條線上，可採用 y = a*x + b這個方式下去做確認。以此概念下去執行複雜度會是 O(n^2)。筆者本來是採用兩層迴圈 
    for i in range(n-1): 
    for j in range(i + 1, n):

    計算所有的 (a, b) 方程組合，但後來發現即便這樣計算，複雜度也還是一樣高；且因為加入了區間 interval 的計算，多了一個需要評估是否會發生浮點數溢位的數值，另外就是把所有兩點組合均放在同一個字典內統計，亦要因此注意重複加入或漏失的狀況；

  2. 針對第一點的狀況，可以使用各點單獨與資料庫內其他點位的計算組合來進行優化：因為兩點中有一點是固定不變的，故只要斜率相同則這些點必定會在同一條線上而不用擔心平移的問題；另外用各點單獨比對也可縮小字典的記憶體需求；
  3. 而在進行斜率計算時需要注意幾個容易出錯的地方：
    1. AB兩點重疊 （x1 == x2 and y1 == y2）　－　這表示當出現任一條線穿過A點時，該線不管怎樣都會穿過B點；
    2. 兩點連線為一水平線（y1 == y2）　－　表示斜率為0；
    3. 兩點連線為一垂直線（x1 == x2）　－　表示斜率為inf，如不將此情況獨立出來在進行斜率計算時便會出現除數為 0 的錯誤。

另外因為網站只提供 python 2.7 IDE，而在 2.7 版本中兩整數相除亦會只是整數而不會變成浮點數，故這部分在進行編碼時要另外留意。

Code:

from collections import defaultdict
class Solution:
    # @param A : list of integers
    # @param B : list of integers
    # @return an integer
    def maxPoints(self, A, B):
        n = len(A)
        output = 0
        if n <= 2: return n
        for i in range(n-1):
            slopeDict = defaultdict(int)
            dup = 0
            for j in range(n):
                if A[i] == A[j] and B[i] == B[j]:
                    dup += 1
                    continue
                elif A[i] == A[j]: slope = float("inf")
                elif B[i] == B[j]: slope = 0
                else:
                    slope = (float(B[i] - B[j])/float(A[i]-A[j]))
                slopeDict[slope] += 1
            if slopeDict:
                temp = max(slopeDict.values())
            else: temp = 0
            temp += dup
            if temp > output:
                output = temp
        return output

GitHub: GitHub

發表留言