旋轉數組（三種解決方案）

将數組元素向右移動k個位置，k非負

文章目錄

• 第一種方案
• 第二種方案
• 第三種方案

第一種方案

解決思路：将數組中的元素複制到一個新數組中，将數組元素依次配置設定到新的位置上

時間複雜度：O(n)

空間複雜度：O(n)

void rotate(int* nums,int numsSize,int k)
{
	k%=numsSize;
	int newArray[numsSize];
	for(int i=0;i<numsSize;i++)
		newArray[i]=nums[i];
	for(int j=0;j<numsSize;j++)
		nums[(j+k)%numsSize]=newArray[j];
}
           

第二種方案

解決思路：先反轉所有的數組元素；再反轉前k個數組元素；最後反轉剩餘的數組元素

時間複雜度：O(n)

空間複雜度：O(1)

void swap(int* x,int* y)
{
	int temp;
	temp=*x;*x=*y;*y=temp;
}
void rotate(int* nums,int numsSize,int k)
{
	k%=numsSize;
	for(int i=0;i<numsSize/2;i++)
		swap(nums+i,nums+numsSize-i-1);
	for(int i=0;i<k/2;i++)
		swap(nums+i,nums+k-i-1);
	for(int i=0;i<(numsSize-k)/2;i++)
		swap(nums+k+i,nums+numsSize-i-1);
}
           

第三種方案

解決思路：利用一個空間儲存數組的第一個元素，計算第一個元素移動後的位置，将該位置上的元素與空間中的元素進行交換，然後繼續計算交換後的元素移動後的位置并重複上述操作

舉一個例子[1,2,3,4,5,6,7]，k=3

利用一個空間temp進行元素之間的交換

(1)temp=1 移動到的位置4 替換後temp=4 [1,2,3,1,5,6,7]
(2)temp=4 移動到的位置7 替換後temp=7 [1,2,3,1,5,6,4]
(3)temp=7 移動到的位置3 替換後temp=3 [1,2,7,1,5,6,4]
(4)temp=3 移動到的位置6 替換後temp=6 [1,2,7,1,5,3,4]
(5)temp=6 移動到的位置2 替換後temp=2 [1,6,7,1,5,3,4]
(6)temp=2 移動到的位置5 替換後temp=5 [1,6,7,1,2,3,4]
(7)temp=5 移動到的位置1 替換後temp=1 [5,6,7,1,2,3,4]
           

但是這樣存在一個隐性的問題，如[1,2,3,4,5,6]，k=3

(1)temp=1 移動到的位置4 替換後temp=4 [1,2,3,1,5,6]
(2)temp=4 移動到的位置1 替換後temp=1 [4,2,3,1,5,6]
           

我們會發現在這種情況下會陷入一個循環（形成了一個圈），在兩個數組元素之間不斷地變換。這時候就需要我們從第二個元素開始再次進行計算。

通過規律我們可以發現，假設數組元素個數為 n n n，形成的圈數為 x x x，形成的圈周遊元素的個數為 y y y，則有 x n = y k xn=yk xn=yk，是以 x n xn xn是 n n n, k k k的公倍數。又因為我們希望經過最少的圈就能回到起點，即算法結束，是以 x x x應該盡可能的小。在這種情況下 x n xn xn應為 n n n和 k k k的最小公倍數，即 x n = l c m ( n , k ) xn=lcm(n,k) xn=lcm(n,k)

x n = l c m ( n , k ) = y k xn=lcm(n,k)=yk xn=lcm(n,k)=yk

y = l c m ( n , k ) / k y=lcm(n,k)/k y=lcm(n,k)/k

一圈我們可以周遊的元素個數為 y y y

是以周遊次數為 n l c m ( n , k ) / k = n k l c m ( n , k ) = g c d ( n , k ) \cfrac{n}{lcm(n,k)/k}=\cfrac{nk}{lcm(n,k)}=gcd(n,k) lcm(n,k)/kn​=lcm(n,k)nk​=gcd(n,k)

是以周遊的次數為 n n n和 k k k的最大公約數

int gcd(int x,int y)
{
	return y?gcd(y,x%y):x;
}
void swap(int* x,int* y)
{
	int temp;
	temp=*x;*x=*y;*y=temp;
}
void rotate(int* nums,int numsSize,int k)
{
	k%=numsSize;
	int count=gcd(k,numsSize);
	for(int i=0;i<count;i++){
		int start=i,temp=nums[start];
		do{
		  	int next=(start+k)%numsSize;
		  	swap(&temp,nums+next);
		  	start=next;
		  }while(start!=i);
	}
]
           

時間複雜度：O(n)

空間複雜度：O(1)