轮转数组的三种解法_给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

LeetCode189题 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
法一：循环移位，直接向右循环k位很难办到，但可以每一轮只循环一位，移动k轮，但同时如果k超出了数组的大小，就会进行无意义的轮换，所以首先让k%numsSize，只进行有意义的轮换

void rotate(int *nums,int numsSize,int k){
	assert(nums);
	k%=numsSize;//只需要进行有效的轮转
	for(i=0;i<k;i++){//代表需要轮转k次
		int tmp=nums[numsSize-1];//之后为轮转过程
		for(j=numsSize-1;j>0;j--){
			nums[j]=nums[j-1];
		}
		nums[0]=tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11

2.数组映射 假设我们有数组[1,2,3,4,5,6],我们想要向右轮转2位，轮转结果为应为[3,4,5,6,1,2]，如果直接向下标加2的位置轮转，数组最右侧数据会发生越界，我们可以对下标取余numsSize大小，即可消除越界，所以需要一个开辟一个数组

void rotate(int *nums,int numsSize,int k){
	assert(nums);
	int* tmp=(int*)malloc(sizeof(int)*numsSize);
    if(tmp==NULL){
    	printf("malloc fail\n");
    	exit(-1);
	}
    for(int i=0;i<numsSize;i++){
        tmp[(i+k)%numsSize]=nums[i];
	}
	for(int i=0;i<numsSize;i++){
		nums[i]=tmp[i];
	}
	free(tmp);
	tmp=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.巧用反转 假设有一个数组[1,2,3,4,5,6]，想要向右轮转2位，结果为[5,6,1,2,3,4]
首先要对k对numsSize取余，才能确保后续操作正确且简洁
该题使用到了三步翻转法，先整体对数组进行反转，再对前k个数进行反转，再对后k个数进行反转
字符串局部反转时，先如同写一个reverse函数

void reverse(int *left,int *right){
	while(left<right){
		int tmp=*left;
		*left=*right;
		*right=tmp;
		left++;
		right--;
	}
}
1
2
3
4
5
6
7
8
9

void rotate(int* nums, int numsSize, int k)
{
    k=k%numsSize;
    reverse(nums,nums+numsSize-k-1);
    reverse(nums+numsSize-k,nums+numsSize-1);
    reverse(nums,nums+numsSize-1);
}
1
2
3
4
5
6
7

注意，无论是左旋数组还是右旋数组，都可以采取反转前k个，再反转后后面numsSize-k个，然后再全部反转