給定一個源和陣列天線的最終，發現跳數在不到二次時間複雜度生成從源最終

Question

假設有一個整數數組（例如爲[1 5 3 4 6]）。元素根據以下規則重新排列。每個元素都可以向前跳躍（向左），並在跳過的索引中滑動元素。該過程以第二索引中的元素開始（即5）。它有跳過元素1的選擇，或者它可以保持在它自己的位置。如果它選擇跳躍，則元素1向下滑動到索引2.讓我們假設它選擇跳躍，然後我們的結果數組將會是[5 1 3 4 6]。元素3現在可以跳過1或2個位置並重復該過程。如果在一個位置上跳躍3次，陣列現在是[5 3 1 4 6]，並且如果跳過兩個位置，現在將是[3 5 1 4 6]。

這是很容易證明的元素的所有可能的排列是可以以這種方式。任何最終配置都可以通過一組獨特的事件來達成。

的問題是，給定一個最終陣列和源陣列，發現在來自光源的陣列天線的最終到達所需要的跳的總數。 O（N^2）實現很容易找到，但我相信這可以在O（N）或O（NlogN）中完成。另外，如果不可能比O（N2）做得更好，那麼知道這一點將是非常好的。

例如，如果最後一個數組爲[3,5,1,4,6]和源陣列[1,5,3,4,6]，答案將是3.

我ö （N2）算法是這樣的：你從源頭數組的所有位置循環遍歷，因爲我們知道這是最後一個要移動的元素。這裏是6，我們檢查它在最終數組中的位置。我們計算所需跳數，並需要重新排列最終數組，以將該元素放置在源數組中的原始位置。重新排列步驟遍歷數組中的所有元素，並且該過程遍歷所有元素，因此O（N^2）。使用散列圖或地圖可以幫助搜索，但是在每個產生O（N^2）的步驟之後需要更新地圖。

P.S.我試圖用貝葉斯方式來模擬兩個排列之間的相關性，這是一個小問題。任何關於修改生成過程以使問題更簡單的想法也是有幫助的。

編輯：我發現我的答案。這正是Kendall Tau距離所做的。有一種簡單的基於合併排序的算法可以在O（NlogN）中找到它。

Answer 1

將目標數組視爲一個排序。目標陣列[2 5 4 1 3]可以被視爲[1 2 3 4 5]，只是通過重新標記。您只需知道映射即可在常量時間內比較元素。在這種情況下，要比較4和5，請檢查：index[4]=2 > index[5]=1（在目標陣列中）等4 > 5（含義：4必須在最後的5的右側）。

所以你真的只是一個香草排序問題。排序與通常的數字排序不同。唯一改變的是你的比較功能。其餘的基本上是一樣的。分類可以在O(nlgn)或甚至O(n)（基數排序）中實現。也就是說，您還有一些額外的限制：您必須在原地進行排序，並且只能交換兩個相鄰的元素。

強大而簡單的候選人將是selection sort，這將做到這一點在O(n^2)時間。在每次迭代中，您都會識別「未放置」部分中的「最左邊」剩餘元素，並交換它，直到它落在「放置」部分的末尾。通過使用適當的數據結構（在O(lgn)時間內識別「最左邊的」剩餘元素的優先級隊列），它可以改進爲O(nlgn)。由於nlgn是基於比較的排序的下限，我真的認爲你可以做得比這更好。

編輯：所以你根本不感興趣的交換順序，只有交換所需的最小數量。這正好是數組中的inversions（適應您的特定需求：「非自然排序」比較函數，但不會改變數學）。請參閱this answer以獲取該斷言的證據。

查找倒數的一種方法是調整合並排序算法。因爲你必須實際對數組進行排序來計算它，結果仍然是O(nlgn)時間。有關實現，請參見this answer或this（同樣，請記住，您必須修改）。

Answer 2

從你的答案我假設跳數是將原始數組轉換爲最終數組所需的相鄰元素的交換總數。

我建議使用類似插入排序，但沒有插入部分 - 數組中的數據不會被改變。

你可以使隊列t作爲帶計數器的平衡二叉搜索樹（子樹中的元素數）。

可以添加元素噸，從噸，平衡噸爲O除去元素和找到元素位置在噸（日誌C）時間，其中C是在噸元件的數目。

找到元素位置的幾句話。它由二進制搜索和跳過的左側（如果您保留分支上的元素，則爲中間元素+1）累計。

關於平衡/添加/移除的幾句話。您必須從已移除/添加的元素/子樹和更新計數器向上遍歷。對於插入+餘額和刪除+餘額，操作總數仍然保持在O（log C）。

讓我們噸是（平衡搜索樹）隊列，p是當前原始數組索引，q被最終數組索引，原數組是一個，最終陣列是˚F。

現在我們已經1個循環從左側開始（說，p = 0，q = 0）：

• 如果一個 [p] == ˚F [q]，則原始數組元素跳過整個隊列。添加t.count至答案，增量p，增量q。

• 如果一個 [p]！= ˚F [q]和˚F [q]不在噸，然後插入一個 [p]到t和增量p。

• 如果一個 [p]！= ˚F [q]和f [Q]是在噸，然後添加F [Q]的在隊列回答位置，取出f [q] from t and increment q。

我喜歡的魔法，這將確保這一進程將p和q移動到陣列的端部在相同的時間，如果陣列是真的一個陣列的排列。不過，您應該檢查p和q溢出來檢測不正確的數據，因爲我們沒有真正快速的方法來證明數據是正確的。