【leetcode】旋转数组【C、Python】，,题目：给定一个数组，

【leetcode】旋转数组【C、Python】，,题目：给定一个数组，

题目：

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3输出: [5,6,7,1,2,3,4]解释:向右旋转 1 步: [7,1,2,3,4,5,6]向右旋转 2 步: [6,7,1,2,3,4,5]向右旋转 3 步: [5,6,7,1,2,3,4]

示例2:

输入: [-1,-100,3,99] 和 k = 2输出: [3,99,-1,-100]解释: 向右旋转 1 步: [99,-1,-100,3]向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为O(1) 的原地算法。

题目分析：

对于像笔者这样的小白来说，拿到这样的题目第一思维是复制一个数组的副本，但题目要求的是“使用空间复杂度为O(1) 的原地算法",所以此方法应该PASS掉。
构思Python解题方案时很容易想到直接去对数组做K轮移动，比如刚开始笔者写出了这样的Python代码：

 1 class Solution: 2     def rotate(self, nums, k): 3         """ 4         :type nums: List[int] 5         :type k: int 6         :rtype: void Do not return anything, modify nums in-place instead. 7         """ 8         for j in range(0,k): 9             temp=nums[len(nums)-1]10             for i in range(0,len(nums)-1):11                 nums[len(nums)-i-1]=nums[len(nums)-i-2]12             nums[0]=temp

错误实例

但事实证明这种方法太低效，没有通过时间复杂度的检验。

笔者忘记了python不同与C的高级功能——切片。

对于用C的解题方式：

有多种解题思路，可以参考这篇博文：https://blog.csdn.net/qq1518572311/article/details/80302654

笔者还尝试了用C++解决这个问题，相对于用C解决此问题，C++的麻烦之处在于需要自己求出数组长度numsSize

笔者了解到在C语言下判断一个数组中含有多少个元素的方法:

1、sizeof(array)/sizeof(array[0])；

2、sizeof(array)/sizeof(数组的类型，如int，double等)

但此方法并不可靠。原因：

开发工具和运行环境的不同，有时sizeof(int)得到的结果不一样，作者在WinTC和VC++中的到的结果分别为2和4，这样就不能得到正确（想要）的结果。

据说是int类型和运行环境有关，在16bits的情况下就是2，32bits的情况下是4。

另外C中规定了每种数据类型的表示范围，但并没有严格规定其字节数。

不得不自己写函数：

 1 #include <stdio.h> 2 int main(void) 3 { 4     int i=0; 5     int nums[]={1}; 6     int numsSize=0; 7     for(i=0;nums[i]!=NULL;i++) 8     { 9         numsSize++;10     }11     printf("%d",numsSize);12     return 0;13 }

数组长度计算

 1 class Solution { 2 public: 3     void rotate(vector<int>& nums, int k) { 4     int i=0;   5     int temp[100]; 6     int numsSize=0; 7     for(i=0;nums[i]!=NULL;i++) 8     { 9         numsSize++;10     }11     for(i=numsSize-1;i>numsSize-1-k;i--)    //没有等于号 i>=numsSize-1-k  12         temp[i+k-numsSize] = nums[i];   //保存被覆盖的数nums[i]  13     for(i=numsSize-1; i>=k; i--)  14         nums[i] = nums[i-k];            //nums[i]被覆盖，提前保存到temp中去， 再nums[i]=移位前一个数  15       16     for(i = 0; i<=k-1; i++)         //赋值  17         nums[i]=temp[i]; 18         19     };20 };

C++解决方案

遗憾的是：当输入数组是只有一个元素的数组时，程序报错，原因至今未查出，希望有路过的大神能指点指点！

错误信息：

执行错误信息：malloc(): memory corruption: 0x000000000258ae90 ***

最后执行的输入：[1] 1

解答代码：
C语言：

 1 void rotate(int* nums, int numsSize, int k) { 2     int now = 0,start = 0, data_to_next = 0, temp = 0;   3     int cnt = numsSize ;//用来表示跳转次数，次数到了，就停止循环   4       5     k = k%numsSize;   6     if(k==0)   7         return;   8    9     for(start = 0;start<numsSize;start++)  10     {  11         now = start;  12         data_to_next =  nums[start%numsSize];   //第一个数，先提出来，用于 与下一个数交换  13         while(1)  14         {  15             now = now+k;  16           17             temp = nums[now%numsSize];           //交换一次         18             nums[now%numsSize] = data_to_next;  19             data_to_next = temp;  20             cnt--;        21               22             if((now%numsSize) == start)         //如果交换到start的开始，就结束本次跳转交换  23                 break;  24                             25         }  26      27         if(cnt==0)  28             break;                  29     }     30   31     32 }

Python：

1 class Solution:2     def rotate(self, nums, k):3         """4         :type nums: List[int]5         :type k: int6         :rtype: void Do not return anything, modify nums in-place instead.7         """8         nums_len = len(nums)9         nums[:] = nums[nums_len - k :] + nums[:nums_len - k]

【leetcode】旋转数组【C、Python】