20200414-邏輯-取得兩條線的交岔節點

(ref from https://t.ly/mZE5p )

緣起

今天上班在找資料時，看到這此Blog的資訊，疑？ 來思考看看如何取得”最佳”結果吧。

而這，感覺就像是 區塊鏈 它的演算法， 要回朔它分岔的節點是那兒？？ (只是這圖是反著畫)

題目

知道開頭的節點 資訊， 而假設 上下為 A、B 線。 何時可以找到它們共同的節點。

假設 A在 第M個 節點，與B在 第N個 節點 交岔。

另(A總共有A個節點、B總共有B個節點數)

思考 + 我的解法：

在原Link下，提供了”基本”解法：

方法一、A線全捉出來，B線一個個比對； 這最多需要： (A) 的 B 次方。( A數+N ) 次  (取出節點次數)

而我的思考邏輯：

(先說這個沒有看網路答案的~~或許有別種解法)

；則 最多需要： MAX(M,N) x2 –1 次的查詢。  (這算是取出節點次數)

做法：

A、B 輪流取一個節點，並將它放入共同的堆疊裡，

而在放入時檢查，是否已存在？ (若已存在，即找到共同的第一個節點)

例如： 放B的第N個節點時，發現已存在，則表示，A 中 M的位置 = 大於 (第一個節點 在堆疊中的 位子 X ) / 2 ) 值的 最小整數。

結論：

當   共同點的數量 > MAX(分岔數量) 時，我的做法才有利。

若   共同點的數量 < MAX(分岔數量) 時，則我的不利 (????)

(THE END)