使用常量內存旋轉m個位置左邊的n個元素的一維數組？

給定一個由n個元素構成的一維數組，以及如何有效地旋轉數組，以使數組中的元素左移m個位置？僅使用常量O（1）內存，是否有可能在O（n）時間複雜度下執行此操作？使用常量內存旋轉m個位置左邊的n個元素的一維數組？

例如，如果n = 8，並且您的數組是[0, 1, 2, 3, 4, 5, 6, 7]，並且您將它向左旋轉m = 2，則會得到[2, 3, 4, 5, 6, 7, 0, 1]。

這是我在Python中實現的一個天真的解決方案，它使用O（n）時間和O（n）內存與臨時數組。

def rotateLeft(A, m): 
    temp = [None]*len(A) 
    for i in xrange(len(temp)): 
     temp[i] = A[(i + m) % len(A)] 
    for i in xrange(len(A)): 
     A[i] = temp[i]

我怎麼能更有效地做到這一點？我被告知這可以用恆定的內存來完成，並且仍然在O（n）時間。

任何語言的解決方案都可以，任何建議都非常值得歡迎。

編輯：我不是在尋找圖書館解決方案。此外，該數組不是鏈接列表/雙端隊列。沒有頭/尾/下一個/前一個元素的概念。

來源

2013-10-08 Shashank

您是否需要專門使用數組？如果你使用了一個LionkedList，你可以在一段時間內完成它：1）從列表的最後一個元素指向第一個元素，2）從第一個元素指向第二個元素。 – LuigiEdlCarno

@LuigiEdlCarno是的，它需要使用一個數組。否則解決方案將是微不足道的。 :) – Shashank

讓我們看看逆轉最終陣列：

[1, 0, 7, 6, 5, 4, 3, 2] (spacing mine)

你看到一些有趣的事情？

來源

2013-10-08 08:12:42 MBo

是的......其實我是。 :)這可能只是我在找的東西。 [1，0]只是[0，1]相反，[7,6,5,4,3,2]只是[2,3,4,5,6,7]相反。因此，由於使用交換反轉大小爲k的數組爲O（k），那麼需要完成的操作是將數組從0反轉爲m，然後將數組從m + 1反轉爲n，最後反轉整個數組。這是線性時間O（n）和常量O（1）存儲器。做得好。 :) – Shashank

+1的想法和它的方式 – Leeor

試着想想這樣的解決方案是什麼樣的。如果你不能使用更多的空間，唯一可用的方法是交換元素。試着用一支筆，用2個元素的數組，然後是3來做。當你明白這個想法時，它應該很容易。

事實上，使用交換需要多一個變量，您可以使用XOR交換算法（http://en.wikipedia.org/wiki/XOR_swap_algorithm）修復此問題，但我認爲這不是很重要。

來源

2013-10-08 07:34:12

交換的單個臨時變量仍然是固定內存。 – Leeor

是的，嚴格來說你是對的 –

由於內存限制，這並不是微不足道的。首先將第一個元素移動到新的位置，並且由於不能存儲太多元素 - 繼續爲剛剛驅逐的元素找到位置。

現在想想通過次數與GCD（n，m）的關係，以及算法應該如何反映這一點 - 以gcd爲1的常見情況開始（例如，如果在上例中m = 3 ） - 一旦替換鏈將結束（您可以通過比較當前索引與您開始的索引來進行檢查），您將完成任務。但是，對於GCD（m，n）> 1，您只能移動部分元素，並且您需要在最後一個元素之後立即啓動一個新元素。

現在說服自己，無論階段的數量如何，完成的班次總數都是O（n）。

來源

2013-10-08 08:01:18 Leeor

看看下面的僞代碼。對我來說似乎是正確的。

function rotate(a[], a.length) 
    { 
    i = 0; 
    j = 0; 
    k = 0; 
    temp = a[0]; 
    k = (i + a.length - 2) % a.length 
    while (j < a.length){ 
    temp1 = a[k] 
    a[k] = temp; 
    i = k; 
    temp = temp1 
    k = (i + a.length - 2) % a.length   
    j++ 
    } 

    }

來源

2013-10-08 09:02:04

減去2（價值米） –

我不認爲這是非常正確的。 – Shashank

這是其通過@MBo向我暗示一個恆定存儲器解決方案。除了陣列空間和m：i，midpoint和endpoint之外，它還使用3個額外變量。它循環3次，首先顛倒兩個子陣列，然後在最後一個循環中顛倒整個陣列。它是O（n/2 + m/2 +（nm）/ 2），它只是O（n），因爲0 < = m < n由於我在開始時做了m = m % n以減少任何給定的正m數組範圍內的索引。

交換也通過2項緩衝區（2元素的元組）發送值，但它仍然是用於交換的常量內存，所以它並不重要。

def rotateLeft(A, m): 
    m %= len(A) 
    # Reverse A[0..m-1] 
    midpoint = m/2 
    endpoint = m-1 
    for i in xrange(midpoint): 
     A[i], A[endpoint-i] = A[endpoint-i], A[i] 
    # Reverse A[m..n-1] 
    midpoint = m+(len(A)-m)/2 
    endpoint = len(A)-1 
    for i in xrange(m, midpoint): 
     A[i], A[endpoint-(i-m)] = A[endpoint-(i-m)], A[i] 
    # Reverses all elements of array in place 
    midpoint = len(A)/2 
    endpoint = len(A)-1 
    for i in xrange(midpoint): 
     A[i], A[endpoint-i] = A[endpoint-i], A[i]

它也允許負轉（旋轉到右邊），這在我看來是非常整齊。這意味着rotateRight可以通過以下方式實現。

def rotateRight(A, m): 
    rotateLeft(A, -m)

然後下面的代碼將通過斷言檢查就好了。

A = [0, 1, 2, 3, 4, 5, 6] 
B = A[:] # Make copy of A and assign it to B 
rotateLeft(A, 4) 
rotateRight(A, 4) 
assert(A == B)

來源

2013-10-08 09:36:14 Shashank

使用常量內存旋轉m個位置左邊的n個元素的一維數組？

回答

相關問題