Leetcode-旋转数组

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

链接：https://leetcode-cn.com/problems/rotate-array/

注意点：

• 当要旋转的次数k大于数组的元素个数时：假设数组的长度为n，每进行n次旋转相当于数组顺序并未发生改变 ==k和n相等，不旋转就是结果==
• 旋转次数大于数组元素个数时，旋转的结果和 ==k = k % n== 结果一致。
• 所以，先判断k和n的关系，也可以不判断，直接使用k = k%n 如果k小于n，k%n的结果还是k

方法1：暴力求解 - 在OJ上过不了

==思路==：每次旋转一个元素，共旋转k次。

• 用临时变量tmp保存最后一个元素，然后前面的元素往后覆盖(从右边开始往后移动，不能从左边开始移动，这样会把数组元素覆盖掉)
• 移动完成后，把tmp保存的元素放到数组第一个位置
• 共执行k次

图解

时间复杂度：O(N*K) 每次挪动N-1个元素，共旋转K次->N*k

空间复杂度：O(1) 每次旋转都重新开辟空间，但是使用的都是上次开辟过的空间，所以本质上之开辟了一个空间，重复利用

代码

void rotate(int* nums, int numsSize, int k)
{
    k = k%numsSize;
    int i = 0;
    for(i = 0;i < k;i++)
    {
        //保留最后元素下标 
        int tmp = nums[numsSize-1];
        // 元素后移
        int j = 0;
        for(j= numsSize -2;j >= 0;j--)
        {
            //先移动后面的元素
            nums[j+1] = nums[j];
        }
        //最后，把tmp的元素放到下标为0位置
        nums[0] = tmp;
    }
}

方法2：空间换时间

==思路==：开辟和原来大小一样的空间

• 旋转k次，本质是把后K个元素按顺序放在前面
• 所以：把后k个元素放到新数组中（倒数第k个元素下标为：n-k 范围为：[n - k,n -1]），再把前n-k个元素接着往下存放(范围为：[0,n - k -1])
• 最后把数组内容拷贝回去

图解

时间复杂度：0(N) 遍历数组，然后把元素拷贝回去->共执行2*N次，前面系数省略

空间复杂度：O(N) 开辟了一个和原数组一样大小的数组

代码

void rotate(int* nums, int numsSize, int k)
{

	//每旋转元素个数次就是恢复到最初的状态
	k %= numsSize;
	//已知的是元素个数为：numsSize
	int* arr = (int*)malloc(sizeof(int) * numsSize);	//开辟相同大小的数组
	int i = 0;
	//倒数第k个元素	*(num+numsSize-k) == num[numsSize-k]
	//1.将倒数第k个元素到最后一个元素移动到新数组
	//用另一个变量count记录新数组的下标
	 int count = 0;
	for (int i = numsSize - k; i < numsSize; i++)
	{
		arr[count] = nums[i];//将需要颠倒的先拷贝过去
		count++;
	}
	//2.将原来剩下元素拷贝过去
	for (i = 0; i < numsSize - k; i++)
	{
		arr[count] = nums[i];
		count++;
	}
	//将新数组的内容拷贝回原来的数组
	for (i = 0; i < numsSize; i++)
	{
		nums[i] = arr[i];
    }
}

方法3：三步逆置法

==思路==：

• 第一步：先逆置后k个元素 (范围：[n - k,n - 1])
• 第二步：逆置前n - k个元素(范围：[0,n - k -1])
• 第三步： 整体逆置 (范围：[0, n -1])

图解

逆置函数 -以区间逆置

void Reverse(int* arr,int* left,int*right)
{
    assert( (left&&right) );
    while(left < right)
    {
		int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        right --;
        left ++;
    }
}

代码

共有numsSize个数，最后一个元素下标为：numsSize - 1

倒数第k个数下标为： numsSize - k

写法1：区间写成 下标形式：

//下标形式：
void Reverse(int* arr,int left,int right)
{
    while(left < right)
    {
		int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        right --;
        left ++;
    }
}
void rotate(int* nums,int numsSize,int k )
{
    //k的值比numsSize大
    //没旋转numsSize次就是原来的元素顺序
    if(k>=numsSize)
    {
        k = k%numsSize;
    }
    //三步逆置法
    //1.前n-k个元素逆置
    Reverse(nums,0,numsSize - k - 1);
    //2.后k个元素逆置
    Reverse(nums,numsSize - k,numsSize-1);
    //3.整体逆置
    Reverse(nums,0,numsSize-1);
}

写法2：区间写成指针形式

void Reverse(int* left,int*right)
{
	while (left < right)
	{
		int tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
void rotate(int* nums,int numsSize,int k )
{
    //k的值比numsSize大
    //没旋转numsSize次就是原来的元素顺序
    if(k>=numsSize)
    {
        k = k%numsSize;
    }
      //指针写法
	Reverse(nums + numsSize-k, nums+numsSize- 1);//后k个逆置
	Reverse(nums, nums + numsSize - k - 1);//前n-k个逆置
	Reverse(nums, nums+numsSize - 1);//整体逆置
}