重新排列旋轉的排序陣列

Question

我已經看到幾個與旋轉排序陣列有關的問題用於搜索主元素或搜索這樣的數組中的元素。

但是我沒有發現任何與有關的問題，將這樣一個數組重新排列爲原始形式而不使用排序。

所以我的問題：*是否有一種有效的方式，或詭計，重新排列旋轉，排序數組原始形式而不使用額外的內存？

Answer 1

繼承人我會做什麼.. 我會找到起始元素使用二進制搜索的變化。

一旦被發現，如果你可以使用外部存儲器，它可以在O（N）來完成 所以總時間爲O（LGN）+ O（N），這是O（n）

具體到輪換：看到阿賈伊的評論，我同意，由於我們必須輪換，最好的選擇是氣泡排序。它是O（n * m），其中m是旋轉元素的數量。

但是，如果我們可以使用一些存儲來保持啓動元素兩側的元素，基本上，如果我們可以使用外部存儲器，它只是將每個元素放在新數組的正確位置的問題。