【leetcode】189.轮转数组_下列程序的功能是定义一个数组,将数组中的元素向右轮转k个位置,其中k是非负数。例

一、题目描述

给一个数组，将数组中的元素向右轮转k个位置，其中k是非负数

 二、思路

1.暴力求解（旋转k次）

先保存最后一个元素，然后整体向后移动，再将保存的元素放到数组的第一个位置

时间复杂度：O(N^2)

空间复杂度：O(1)

思路1的效率超时，所以在oj中不能通过

2.用空间换时间

用一个新的数组先存放要旋转的元素（k个元素），然后再将剩余的元素拷贝到新的数组中，最后再将新数组中的内容拷贝到原数组中

3.三步翻转法

将后k个元素旋转，剩余元素再旋转一次，再整体旋转

三、实现

思路1：

#include<stdio.h>
//轮转数组
void rotate(int* nums, int numsSize, int k)
{
	
	while (k--)
	{
		int tmp = nums[numsSize - 1];
		for (int i = numsSize-1; i >0 ; i--)
		{
			nums[i] = nums[i - 1];
		}
		nums[0] = tmp;
	}
}
 
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	int k = 3;
	int sz = sizeof(arr) / sizeof(arr[0]);
	rotate(arr, sz, k);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

思路2：

    void rotate(int* nums,int numsSize,int k{
    //用空间换取时间
    int* arr=(int*)malloc(numsSize*sizeof(int));
    k%=numsSize;
    //将后k个放到新数组中
    for(int i=0;i<k;i++)
    {
        arr[i]=nums[numsSize-k+i];
    }
    //将元素中剩余元素放到新数组中
    for(int i=0;i<numsSize-k;i++)
    {
        arr[k+i]=nums[i];
    }
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=arr[i];
    }
    free(arr);
    arr=NULL;
}

注意：这里的k%=numsSize，如果说数组中只有一个元素，而k=2，此时会发生越界访问

假设我们一共有五个元素，当k=5的时候，就是员顺序保持不变，当k=6时，相当于向右旋转1个元素

思路3：

void reverse(int*str,int left,int right)
{
    
   while(left<right)
   {
       int tmp=str[left];
       str[left]=str[right];
       str[right]=tmp;
       left++;
       right--;
   }
    
}
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}