數滿足關係

Question

給定兩個數組中的元素：

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

計數數量的元件x, y滿足該x是在兩個陣列y之前的狀態。

---

迄今取得的進展：

排序陣列通過它們的索引。例如，這將是：

     object: 1 2 3 4 5 6 7 
indexes in the first array: 6 0 4 3 1 2 5 
indexes in the secnod array: 1 3 4 6 0 2 5 

並將每個元組與另一個元組進行比較。如果元組a的索引低於或高於元組b，則增加滿足條件的元素數。

這具有（N^2）/ 2的時間複雜度，所以O（N^2）太慢了。我明白，沒有更好的最壞情況複雜性，但我最感興趣的是平均結果。所以：有更好的方法/算法嗎？

我想過使用傳遞屬性（如果(x,y)和(y,z)滿足條件，那麼(x,z)也滿足），但沒有運氣。

---

測試用例

對於數組：

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

滿足條件的對是：

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7) 

對於數組：

1 2 3 4 5 6 7 
1 2 3 4 5 6 7 

滿足條件的對是：

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7) 

Answer 1

我非常喜歡在思考這個問題。它確實感覺像是一個CS作業問題，所以我會嘗試去觸及概念而不解決所有問題。

海灘男孩原則

的術語，用我的微積分的老師，實際上解決的技術非常適用問題。基本上，如果你遇到了一個棘手的問題，那就說「如果......」不會很好，並且看看有沒有什麼能讓事情變得更簡單。如果有，請看看你是否可以這樣做。

在這種情況下，如果頂部陣列已經訂購併且僅僅是[1, 2, 3 ...]？這將使解決這個問題變得更容易，因爲它將兩個數組問題變成一個數組問題。

嗯，它可以這樣！您可以將這些問題中的任何一個映射到具有有序第一個數組的映射中。

你列出的第一個例子：

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

我認爲，上述問題等價於下面的問題：

1 2 3 4 5 6 7 
2 7 3 1 5 6 4 

映射

我只是做了一個簡單密碼替換2-> 1 5-> 2 6-> 3 4-> 4 3-> 5 7-> 6 1-> 7（爲什麼這個特殊映射？）。這使問題的基本結構相同。然後你可以解決這個問題，然後撤消你的映射。

你會發現這種將一個問題映射成一個更簡單問題的技術經常出現在計算機科學中，特別是在算法和可計算性類中。

您現在有一個單一的陣列問題找出所有對：

2 7 3 1 5 6 4 

這樣做的時間複雜度我留下一個練習給讀者。

P.S.不要忘記撤消映射的時間複雜性。有時候你會解決一個問題，認爲它很容易發現構建和解構你的映射是非常昂貴的，你必須回到繪圖板。