二（2）OJ题：旋转数组

二（2）OJ题：旋转数组

目录

题目

解答

思路1：暴力求解，多次旋转

思路2：使用额外的数组

思路3：数组翻转

---

题目

力扣https://leetcode-cn.com/problems/rotate-array点击上面网址可查看原题

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

解答 思路1：暴力求解，多次旋转

把最后一个数拿出来，前面的数往后挪，再把最后一个数放到前面，这就是旋转一次，总共旋转k次，k次循环。

时间复杂度O(N*K)，空间复杂度：O(1)

这个OJ暴力求解过不去，时间限制超时

思路2：使用额外的数组

开辟额外空间，以空间换时间。

我们可以使用额外的数组来将每个元素放至正确的位置。用n表示数组的长度，我们遍历原数组，将原数组下标为i的元素放至新数组下标为（i+k）mod  n  的位置，最后将新数组拷贝至原数组即可。

时间复杂度O(N)，空间复杂度O(N)

 我的错误写法，大家可以看看为什么错了，只怪我学艺不精

void rotate(int* nums, int numsSize, int k){
    int *a=(int*)malloc(sizeof(int)*numsSize);
    for(int i=0;i 
总结：因为nums是个一级指针，是实参的一份拷贝；在这个函数中将nums的指向修改了之后，并不会改变外面的数组指向。如果真的要改的话，得传二级指针。
 
因此，这里我们只能把新创建的数组里的值再依次放回到nums数组里面
 
正确代码如下
 
void rotate(int* nums, int numsSize, int k){
    int *a=(int*)malloc(sizeof(int)*numsSize);
    for(int i=0;i 
 Note:开辟的空间最后是要释放的，否则会造成内存泄漏，我们写代码要稍微严谨一点；力扣官方答案没有free可能是因为：这个函数调用了之后，程序就退出了，所以没有free释放，反正程序退出的时候进程就销毁了，所有空间都会释放
 
思路3：数组翻转 
 
 
当我们将数组的元素向右移动k次后，尾部k个元素会移动至数组头部，其余元素向后移动k个位置。
 
 
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的k个元素就被移至数组头部，然后我们再翻转[0,k-1]区间的元素和[k,n-1]区间的元素即能得到最后的答案。
 
 
 
 
我们按上面思路写出下面代码，却发现有小的错误
 
void Reverse(int* nums,int left,int right){
    while(left<=right){
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    Reverse(nums,0,numsSize-1);
    Reverse(nums,0,k-1);
    Reverse(nums,k,numsSize-1);
}
 
 
 
这时我们运行OJ发现一个小的陷阱，如果k比数组长度numsSize大该怎么办呢？
 
 
当k=numsSize时，相当于不旋转，不旋转就是要的结果
 
 
当k>numsSize（比如k=10，numsSize=7），这时相当于旋转3次
 
 
因此我们只需要稍微修改一下，就是正确的代码了
 
void Reverse(int* nums,int left,int right){
    while(left<=right){
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    Reverse(nums,0,numsSize-1);
    Reverse(nums,0,k-1);
    Reverse(nums,k,numsSize-1);
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5580876.html