旋转数组的三种解法

本文涉及的产品
实时数仓Hologres,5000CU*H 100GB 3个月
实时计算 Flink 版,1000CU*H 3个月
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
简介: 本题为数组旋转问题,要求将数组向右循环移动k次。直接模拟会超时,故采用三种优化方法:一、额外数组法,时间空间复杂度均为O(n);二、环状替换,通过最大公约数计算遍历次数,空间复杂度O(1);三、数组翻转,先整体翻转再分段翻转,实现高效原地旋转。


前提概要与题目分析

这道题的基础思路类似于字符串左旋,即先把数组最后一个元素存起来,所有前numsSize-1个元素向后移一次(从后往前)

代码如下:

void rotate(int* nums, int numsSize, int k) {
int tmp=0;
k%=numsSize;
for(int i=0;i=0;j--)
{
nums[j+1]=nums[j];
}
nums[0]=tmp;
}
}
但是这个方法有个严重的问题是当数组元素和循环次数多了后会超出规定的时间限制

因此需要改变一下思路:

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

void rotate(int* nums, int numsSize, int k) {
int newnums[numsSize];
for(int i=0;i<numsSize;i++)
{
newnums[(k+i)%numsSize]=nums[i];
}
for(int i=0;i<numsSize;i++)
{
nums[i]=newnums[i];//拷贝数组
}
}
这里的时间复杂度和空间复杂度都是O(n)(n是数组长度)

方法二:环状替换
以上的公式推导为下面的代码作为铺垫

方法分析:

在这个方法中采用了在原数组的基础上进行位置更新的方法以避免额外开辟新的数组浪费空间,操作方法是从数组首元素开始,将首元素current拷贝到tmp临时变量中,然后跳跃k个元素,将第k个元素和tmp交换,后第k个元素作为current继续拷贝跳跃交换,不断循环直到current回到首元素,以上算遍历一次。

关于遍历的次数,用到了数学公式推导,由公式:

a(回到current所用的圈数)×n(数组元素个数)=b(一次遍历的元素个数)×k(旋转个数/跳过元素个数)

可知:an是n的倍数,an=bk也是k的倍数,因此an是n和k的公倍数(为了将未知量用已知量n,k表示)

由于遍历至current回到原点就结束,因此a要为最小圈数,an就是n,k的最小公倍数,即b=lcm(n,k)/k,所以遍历的次数就是n/b即nk/lcm(n,k)(两数相乘除以两数的最小公倍数=两数的最大公约数)因此求遍历的次数就是求n和k的最大公约数。

另外每个元素只会被遍历一次。

代码如下:

int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}

void swap(int a, int b) {
int t = a; a = b, b = t;
}

void rotate(int* nums, int numsSize, int k) {
k = k % numsSize;
int count = gcd(k, numsSize);//求最大公约数
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % numsSize;
swap(&nums[next], &prev);
current = next;
} while (start != current);
}
}
如果无法理解公式推导可使用单独的变量 count 跟踪当前已经访问的元素数量,当 count=n 时,结束遍历过程。

int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}

void swap(int a, int b) {
int t = a; a = b, b = t;
}

void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;
int count=0;
int start=0;
while(count<numsSize)
{
int current=start;
int prev=nums[start];
do{
int next=(current+k)%numsSize;
swap(&prev,&nums[next]);
current=next;
count++;
}while(start!=current);
start++;
}
}

方法三:数组翻转
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 k%n 个元素会移动至数组头部,其余元素向后移动 k%n 个位置。

该方法为数组的翻转:我们可以先将所有元素翻转,这样尾部的 k%n 个元素就被移至数组头部,然后我们再翻转 [0,k%(n−1)] 区间的元素和 [k%n,n−1] 区间的元素即能得到最后的答案。

void swap(int a, int b) {
int t = a; a = b, b = t;
}

void reverse(int* nums, int start, int end) {
while (start < end) {
swap(&nums[start], &nums[end]);
start += 1;
end -= 1;
}
}

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);
}

另外如果是字符串的话还可以用stract函数做拼接实现旋转

相关文章
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1300 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1327 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
181 82
2025年阿里云域名备案流程(新手图文详细流程)
|
7天前
|
前端开发
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
242 127