自学内容网 自学内容网
自学内容网 > 正文

【C】复杂度算法题 -- 旋转数组

🕗 发布于 2025-01-14 15:01 算法  

  学习完时间复杂度和空间复杂度之后，我们就可以应用学过的知识来算法题了，接下里就有一道跟这个有关的算法题 —— 旋转数组。
leetcode旋转数组icon-default.png?t=O83Ahttps://leetcode.cn/problems/rotate-array/description/

接下来我们来看一下题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

再看一个示例：

输入: nums = [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]

这个题目是刚开始给了这么一个函数，其中nums是指要轮转的数组，numSize是要轮转数组的大小，也就是个数，k是要轮转的字符个数。

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

  这个题目是想要给定一个数组，然后调用rotate函数，在rotate函数中，传入数组首元素的地址，数组的大小，以及要轮转的字符个数，在rotate函数里会实现数组的轮转，让你补齐rotate函数。

1  思路1

  要实现数组的轮转，只需要先让第一个元素后面的元素依次先向后挪动一位，然后把数组最后一个元素挪到第1位，循环k次，就可以实现数组的轮转了，循环过程如图所示：

有了思路就可以写出代码了：

void rotate(int* nums, int numsSize, int k)
{
  while (k--)
  {
    int end = nums[numsSize - 1];
    for (int i = numsSize - 1;i > 0;i--)
    {
      nums[i] = nums[i-1];
    }
 
    nums[0] = end;
  }
}

我们可以分析一下这个数组的时间复杂度与空间复杂度：

时间复杂度：可以看到代码里面有两个循环，第一个循坏是用 k 来控制循环次数，然后内层循环是通过numsSize控制循环次数，这里都假设这两个参数输入的值都是n，所以不难推测出nums[i] = nums[i - 1]语句执行的次数为n^2次，所以时间复杂度就为O(n^2)。

空间复杂度：代码在执行过程中，并没有额外开辟空间，所以空间复杂度为O(1)。

  在leetcode上运行的时候，可以看到这样一个错误：超出时间错误

  其原因就在于时间复杂度太高了，在leetcode上一般时间复杂度为n^2的算法都会超出时间限制。

2  思路2

  再上一个思路里面，时间复杂度太高的原因就在于一个循环里面又嵌套了一个循环，所以我们就有一个思路就是可以把循环嵌套改成两个并列的循环，这样执行次数就从n^2次变成了2n次，所以时间复杂度就变成了O(n)。

  转变成2个并列的循环的话，就需要借助一个新开辟的数组(newArr)，先将经过k次旋转后的数据挪到新数组中，这个过程是通过下标来实现的，首先有一个循环变量i，i从0开始，每次++，知道走到原数组的最后一个下标，然后让newArr[ (i + k) % numsSize] = nums[i]，再将新数组的数据依次挪到原数组中。

 代码实现：

void rotate(int* nums, int numsSize, int k)
{
  //开辟新数组
  int* newArr = (int*)malloc(sizeof(int) * numsSize);
  //开辟失败
  if (newArr == NULL)
  {
    //打印错误信息
    perror("malloc fail！\n");
    exit(1);//退出
  }

  for (int i = 0; i < numsSize;i++)
  {
    newArr[(i + k) % numsSize] = nums[i];
  }
  //把新数组的数据再放回原数组
  for (int i = 0; i < numsSize;i++)
  {
    nums[i] = newArr[i];
  }

}

  写完代码之后，时间复杂度和空间复杂度就很容易分析了，由于并列了两个循环，所以总执行次数为2n次，所以时间复杂度为O(n)，而由于在运行过程中，动态开辟了numsSize个空间，所以空间复杂度为O(n)。

  这样的代码是一种以空间换时间的做法，浪费了空间，却换来了时间效率的提高，那有没有一种时间复杂度为O(n)，而空间复杂度为O(1)的算法呢？

3  思路3

  第三种思路就是充分采用了逆置的思想，这里的逆置举个例子就是：假如有1,2,3,4这四个数字，把这四个数字逆置的话，就是4,3,2,1。

  思路3的思路就在于先把前 numsSize - k 个数据逆置，然后再把后k个数字逆置，然后整体逆置，就达到了旋转k个数字的效果。

  如：

代码实现：

void Swap(int* x, int* y)//交换两个元素的函数
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

void Reverse(int* arr, int left, int right)//逆置函数
{
  while (left < right)
  {
    Swap(&arr[left], &arr[right]);
    left++;
    right--;
  }
}

void rotate(int* nums, int numsSize, int k)
{
  k %= numsSize; //防止k超过数组长度
  //先让前numsSize - k个元素逆置
  Reverse(nums, 0, numsSize - k - 1);//这里要传下标
  //再让后k个元素逆置
  Reverse(nums, numsSize - k, numsSize - 1);
  //整体逆置
  Reverse(nums, 0, numsSize - 1);
}

   然后来分析一下时间复杂度和空间复杂度：

  时间复杂度：在三个函数里面，涉及循环的就是Reverse函数，而在Reverse函数控制循环的条件为left<right，这里的left和right之间的差值最大就是数组的长度，这里假设数组的长度为n的话，每次循环都会让left++，right--，当left大于right的时候，循环就停止了，所以实际上这个循环执行的次数最多也就是n次，所以时间复杂度为O(n)。

  空间复杂度：在执行过程中，用的数组都是原数组，所以没有额外开辟空间，所以空间复杂度为O(1)。

4  共勉

  刚开始学数据结构与算法的时候，可能只能想到第一种暴力求解算法，但是没有关系，刚开始学的时候只想到第一种是正常的，没有一个人生来就会想到后面两种算法思想，但是通过后面的学习，相信我们肯定可以想到好的甚至更好的算法思想，加油！！！


原文地址：https://blog.csdn.net/L_0907/article/details/143840761

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2025