C語言輪轉(zhuǎn)數(shù)組的三種實現(xiàn)

更新時間：2023年08月24日 11:30:29 作者：oulaqiao

輪轉(zhuǎn)數(shù)組是一種將數(shù)組元素循環(huán)移動的處理方式,它通常用于解決一些需要對固定長度的數(shù)組進行循環(huán)滾動處理的問題,本文就介紹了C語言輪轉(zhuǎn)數(shù)組的三種實現(xiàn),感興趣的可以了解一下

題目：

解法1：把最后一位數(shù)字移動到數(shù)組的第一位，然后將第二位開始的每一位往前移動一位
這種方法的時間復雜度=O（N^2）
空間復雜度=O（1）

rotate(int* arr, int n, int k)
{
	k %= n;
	int i = 0;
	for (i = 0; i < k; i++)//旋轉(zhuǎn)k次
	{
		int tmp = arr[n - 1];//把最后一個數(shù)拿出來賦給tmp
		//剩余元素整體向后移動
		int j = 0;
		for (j = n - 1; j > 0; j--)
		{
			arr[j] = arr[j - 1];
		}
		arr[0] = tmp;//把最后一個值賦給數(shù)組的首元素處
	}
	int a = 0;
	for (a = 0; a < n; a++)
	{
		printf("%d", arr[a]);
	}
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	scanf("%d", &k);
	rotate(arr, n, k);
	return 0;
}

解法2：重新創(chuàng)建一個數(shù)組，把需要旋轉(zhuǎn)的拿幾個數(shù)字放在數(shù)組中，然后再把剩余的數(shù)放到這個新數(shù)組的后面
這種方法的時間復雜度=O（N）
空間復雜度=O（N）

void rotate(int* nums, int numsSize, int k) 
{
	int* tmp = (int*)malloc(sizeof(int) * numsSize);//開辟大小為n的動態(tài)內(nèi)存
	k = k % numsSize;
	memcpy(tmp, nums + numsSize - k, sizeof(int) * k);//把旋轉(zhuǎn)的數(shù)拷貝到新數(shù)組中
	memcpy(tmp+k, nums, sizeof(int) * (numsSize-k));//剩下的數(shù)拷貝到新數(shù)組的后面
	memcpy( nums,tmp,  sizeof(int) * numsSize);//把新數(shù)組拷貝給原來的數(shù)組
	free(tmp);
}

解法3：原地解決（三旋法）——最優(yōu)法
這種方法的時間復雜度=O（N）
空間復雜度=O（1）

void reve(int arr[], int left, int right)//逆置函數(shù)，三個逆置都適用
{
	while (left < right)
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
rotate(int* arr, int n, int k)
{
	k %= n;
	reve(arr, n - k, n - 1);//逆置后面的數(shù)
	reve(arr, 0, n - k - 1);//逆置前面的數(shù)
	reve(arr, 0, n - 1);//整體逆置
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	scanf("%d", &k);
	rotate(arr, n, k);
	return 0;
}

到此這篇關于C語言輪轉(zhuǎn)數(shù)組的三種實現(xiàn)的文章就介紹到這了,更多相關C語言輪轉(zhuǎn)數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: