旋轉字符串的就地O（N）

我遇到了一個簡單的（我認爲）旋轉字符串的鍛鍊：旋轉字符串的就地O（N）

要以K字旋轉字符串意味着從開始和傳輸切口這些字符他們到最後。如果K爲負值，則個字符，反之應該從末尾轉移到開始。

我立即發明了使用兩個子串連接的解決方案。然而，我發現下面的加法：

如果你想更嚴峻的挑戰
，我們鼓勵你「就地」進行旋轉

任務是從here - 可以肯定，這不是我高校分配等

我看不到任何簡單的方法來做到這一點（我想應該有O（N）算法）。如果我將第0個字符複製到臨時變量並將第K個字符複製到它的位置，那麼將第2個字符複製到第K個位置等等 - 如果K和字符串長度是共素，我將成功。我認爲我可以管理與其他Ks增加外部循環重複從第1個字符，然後第2等過程 - 我認爲達到GCD（K，strlen（S））

但它看起來太笨拙。

來源

2013-10-11 Alumashka

你想O（n）空間複雜度（在內存中的n個字符串）或O（n）的時間複雜度（本質上每個字符一個操作）或兩者？ – cyphar

「in-place」的意思是O（1）的空間複雜度，所以O（N）當然是關於時間複雜度的。感謝您的澄清！ – Alumashka

[算法在線性時間旋轉數組]的可能的副本（http://stackoverflow.com/questions/4457277/algorithm-to-rotate-an-array-in-linear-time） – Dukeling

讓我們看一下旋轉它由6個字符：

Original: 123456789 
Desired: 789 123456

現在看看，當我們扭轉所需的字符串的兩個部分會發生什麼：

987 654321

這僅僅是原始字符串的逆。

所以，我們需要做的是首先顛倒字符串，然後顛倒兩個部分。

在線性時間就地反轉字符串很容易。

這是最近問的另一個問題的副本，回答它似乎比找到重複更少的努力 - 我只會做這個社區維基。

來源

2013-10-11 10:57:59 Dukeling

哦，我現在看到了。這真的很酷，謝謝！換句話說，我們可以將字符串反轉兩次 - 第一次是關於它的中心，第二次是關於「center + K/2」的 - 我會檢查這個... – Alumashka

旋轉字符串的就地O（N）

回答

相關問題