LeetCode.189(轮转数组)

对于轮转数组这个题,文章一共提供三种思路,对于每种思路均提供其对应代码的时间、空间复杂度。

目录

1. 创建变量来保存最后一个数,并将其余数组向前挪动一位 :

1.1 原理解析:

1.2 代码实现:

 2.创建一个数组,用于存放需要旋转的元素,并放到相应位置:

2.1 原理解析:

2.2 代码实现:

3. 先左部分右旋,再右部分右旋,最后整体逆序(三段逆序法):

3.1 原理解析:

 3.2 代码实现:


题目要求如图所示:

 

1. 创建变量来保存最后一个数,并将其余数组向前挪动一位 :

(注:第一种思路虽然可以解决问题,但是代码的时间复杂度为O(N^2),空间复杂度为O(1),时间复杂度不符合LeetCode的提交标准,所以,第一种思路仅供参考与扩展。)

1.1 原理解析:

 假设一个数组为:

nums[7] = {1,2,3,4,5,6,7};

为了方便表示,用下图来代表数组及数组中的元素:

第一步:先将数组种最后一位元素,即:7,用一个临时变量保存。

 

第二步:将其他剩余元素全部向右移动一位。

 

第三步: 把临时变量保存的7,放到数组的首元素的位置。

 

 至此,完成一次交换。

1.2 代码实现:

用代码表示上述过程,即:

#include<stdio.h>
#include<assert.h>
void rotata(int* nums,int numsize)
{
	assert(nums);
	int tmp = nums[numsize - 1];//用临时变量保存数组最后一个元素
	int i = 0;
	for (i = 6 ; i > 0; i--)
	{
		nums[i] = nums[i - 1];//将其余元素向右移动一位
	}
	nums[0] = tmp;//将临时变量保存的元素放在数组首个元素的位置
}
int main()
{
	int nums[7] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	rotata(nums, sz );
	return 0;
}

打印结果如下:

 

上面的代码,只能实现右移一位。对于移动多个元素,可以将上面移动一个元素的过程用循环来进行。例如,用变量k来代表旋转的次数,代码为:

#include<stdio.h>
#include<assert.h>
void rotata(int* nums,int numsize,int k)
{
    k = k % numsize + 1;//防止k过大,使k的范围在0-7
	assert(nums);
	int j = 0;
	for (j = 0; j < k; j++)
	{
		int tmp = nums[numsize - 1];//用临时变量保存数组最后一个元素
		int i = 0;
		for (i = 6; i > 0; i--)    //0 1 2 3 4 5 6 
			                       //  1 2 3 4 5 6
		{
			nums[i] = nums[i - 1];//将其余元素向右移动一位
		}
		nums[0] = tmp;//将临时变量保存的元素放在数组首个元素的位置
	}
	
	
}
int main()
{
	int nums[7] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int k = 0;
	scanf("%d", &k);
	rotata(nums, sz,k );
	int i = 0;

	return 0;
}

因为数组每旋转7次,数组中的元素就回到不旋转的位置,所以,即使在输入旋转次数为77次时,得到的效果也和旋转一次一样

旋转一次效果:

旋转两次效果:

 

旋转77次:

 

但是,当k的值过大时,因为每右旋7次就是一个循环,所以,为了减少编译器的工作量,用k%numsize+1,让k的取值范围保持在0\rightarrow 7这个区间(闭区间)

 2.创建一个数组,用于存放需要旋转的元素,并放到相应位置:

方法二的时间复杂度为O(N),空间复杂度为O(N)

2.1 原理解析:

依旧使用上面的图来解释思路:

右旋一次:

 右旋两次:

对于上面的两种情况,不难发现,其实所谓的右旋,可理解为将需要进行右旋的元素看成一个整体,让后放到其余元素的前面,例如旋转两次时:

第一步:将元素6,7看作一个整体,其余元素看成一个整体。

 

第二步:作为整体的6,7放到剩余元素的前面进行整合:

 

2.2 代码实现:

有了解决问题的思路后,下面给出具体实现的代码:

void rotate(int* nums, int numsSize, int k){
   int n = numsSize;
   int* tmp = (int*)malloc(sizeof(int)*(n));
  
   k = k%n;

   memcpy(tmp,nums+n-k,sizeof(int)*(k));
   memcpy(tmp+k,nums,sizeof(int)*(n-k));
   memcpy(nums,tmp,sizeof(int)*(n));

   free(tmp);

}

 整体代码的逻辑为: n是数组中元素的个数,k是执行右旋的次数。

1.先用malloc开辟一块空间 

2.用k%n来限制k的取值范围。

3.先利用memcpy函数将nums数组种起始地址n+k,数量为k的元素拷贝到tmp这个临时空间种。

4.再利用memcpy函数将nums剩余的元素拷贝到tmp中。

此时,tmp已经存储了旋转后的数组。

5.将tmp中的元素赋值到nums中。

执行结果如下:

 从结果中可以看到,方法二是用空间来换取速度的方法。

3. 先左部分右旋,再右部分右旋,最后整体逆序(三段逆序法):

最优解法,时间复杂度为O(N),空间复杂度因为只创建了一个额外的临时变量,为O(1)

3.1 原理解析:

对于三段逆序法,同样使用图片来解释:

假设:数组名为nums,数组中的元素个数为n,按照LeetCode中7个元素。需要旋转的位数为k。下面的代码就拿k = 3来解释。

第一步:先将左部分元素整体逆序,即:把下标从0到nums-k-1(即数组中第一个到第四个元素逆序)的元素逆序:

 

第二步:将右半部分元素整体逆序,即:把下标为nums - kn-1(即数组中第五个到第七个元素逆序):

第三步:整体逆序:即:对下标从0到nums-1的元素逆序:

通过LeetCode网站给出的样例发现,整体逆序后结果与样例相同:

 

 3.2 代码实现:

  在上面的解释中,既然每一步都需要逆序,所以,为了方便并且减少代码量,可以提前封装一个交换函数或者直接使用交换函数,这里给出提前封装交换函数的代码:

其中:变量a对应数组nums,变量left对应交换的起始位置,变量right对于交换的结束位置

void reserve( int*a,int left,int right)
{
    while(left < right)
    {
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        left++;
        right--;
    }
}

再交换后,根据上面对原理的解释,对逆序函数进行三次调用并传递相应的参数即可:

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

   int n = numsSize;
   k = k%n;
   reserve(nums,0,n-k-1);
   reserve(nums,n-k,n-1);
   reserve(nums,0,n-1);

}

整体函数如下:

void reserve( int*a,int left,int right)
{
    while(left < right)
    {
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
        left++;
        right--;
    }
}


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

   int n = numsSize;
   k = k%n;
   reserve(nums,0,n-k-1);
   reserve(nums,n-k,n-1);
   reserve(nums,0,n-1);

}

运行结果如下:

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/47044.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Ftp和UDP的区别之如何加速文件传输

FTP&#xff08;文件传输协议&#xff09;是一种传输大文件的老方法&#xff0c;它的速度慢&#xff0c;而且容易受到网络环境的影响。在当今这个文件越来越大&#xff0c;项目交付时间越来越紧&#xff0c;工作分布在全球各地的时代&#xff0c;有没有办法让 FTP 加速呢&#…

重学C++系列之const与static关键字分析

前言 本篇幅讲解关键字const与static&#xff0c;主要围绕在类的范围内叙述&#xff0c;包括作用和使用场景等。 一、const与static的作用 1、const修饰的成员变量&#xff0c;成员变量初始化后不能再修改。 2、const修饰的成员函数&#xff0c;成员函数不可以修改成员变量&am…

数值线性代数:知识框架

记录数值线性代数研究的知识框架。 软件包线性方程组直接法Guass消元法/LU分解、Cholesky分解 LAPACK oneAPI MKL ARPACK Octave 迭代法Jacobi迭代、SOR迭代、共轭梯度法最小二乘特征值/特征向量非对称幂法、QR、Arnoldi分解对称QR、Jacobi、二分法、分治法、SVD 参考资料 G…

PDF添加水印以及防止被删除、防止编辑与打印

方法记录如下&#xff1a; 1、添加水印&#xff1b; 2、打印输出成一个新的pdf&#xff1b; 3、将pdf页面输出成一张张的图片&#xff1a;&#xff08;福昕pdf操作步骤如下&#xff09; 4、将图片组装成一个新的pdf&#xff1a;&#xff08;福昕pdf操作步骤如下&#xff09;…

多线程面试题--使用场景

线程池使用场景&#xff08;CountDownLatch、Future&#xff09; 在使用的时候&#xff0c;首先会给一个初始值&#xff0c;比如图中是3&#xff0c;然后在其他线程中调用countdown&#xff08;&#xff09;方法&#xff0c;当count0则继续执行 多线程使用场景一&#xff08; e…

【Spring Boot】Web开发 — 数据验证

Web开发 — 数据验证 对于应用系统而言&#xff0c;任何客户端传入的数据都不是绝对安全有效的&#xff0c;这就要求我们在服务端接收到数据时也对数据的有效性进行验证&#xff0c;以确保传入的数据安全正确。接下来介绍Spring Boot是如何实现数据验证的。 1.Hibernate Vali…

Python爬虫实战(基础篇)—4获取古诗词给孩子学习(附完整代码)

今天我们来获取古诗词网站的一些古诗词来提供给孩子们学习 PS前面几节课的内容在专栏这里&#xff0c;欢迎大家考古&#xff1a;点我 首先我们看一下网站&#xff1a;点我&#xff0c;今天我们来获取一下【唐诗三百首】 第 1 步&#xff1a;网页分析 在网页中我们发现有许多以…

mysql -速成

目录 1.概述 1.3SQL的优点 1.4 SQL 语言的分类 2. 软件的安装与启动 2.1 安装 2.2 MySQL服务的启动和停止 2.3 MySQL服务的登录和退出 ​编辑 2.4 mysql常用命令 2.5 图形化用户结构Sqlyong 3.DQL 语言 3.1 基础查询 3.1.1、语法 3.1.2 特点 3.2 条件查询 3.2.1 …

N位分频器的实现

N位分频器的实现 一、 目的 使用verilog实现n位的分频器&#xff0c;可以是偶数&#xff0c;也可以是奇数 二、 原理 FPGA中n位分频器的工作原理可以简要概括为: 分频器的作用是将输入时钟频率分频,输出低于输入时钟频率的时钟信号。n位分频器可以将输入时钟频率分频2^n倍…

SQL-每日一题【620.有趣的电影】

题目 某城市开了一家新的电影院&#xff0c;吸引了很多人过来看电影。该电影院特别注意用户体验&#xff0c;专门有个 LED显示板做电影推荐&#xff0c;上面公布着影评和相关电影描述。 作为该电影院的信息部主管&#xff0c;您需要编写一个 SQL查询&#xff0c;找出所有影片…

【Spring框架】spring对象注入的三种方法

目录 1.属性注入问题&#xff1a;同类型的Bean存储到容器多个&#xff0c;获取时报错的问题&#xff1b;1.将属性的名字和Bean的名字对应上。2.使用AutoWiredQualifier来筛选bean对象&#xff1b; 属性注入优缺点 2.Setter注入Setter注入优缺点 3.构造方法注入&#xff08;Spri…

【Android知识笔记】UI体系(一)

Activity的显示原理 setContentView 首先开发者Activity的onCreate方法中通常调用的setContentView会委托给Window的setContentView方法: 接下来看Window的创建过程: 可见Window的实现类是PhoneWindow,而PhoneWindow是在Activity创建过程中执行attach Context的时候创建的…

0-超级计算机

超级计算机 概述主要特点处理能力并行处理大规模存储应用领域能耗云超算 中国超算流行体系结构片内异构节点内异构 概述 当谈到超级计算机时&#xff0c;我们指的是性能超高、处理能力强大的计算机系统。 它们通常由数以千计的处理器核心组成&#xff0c;并具备大规模的内存和…

小程序如何将商品添加到分类

​将商品添加到分类是非常重要的功能&#xff0c;可以让商家更方便地管理分类和商品。下面将具体介绍如何将产品添加到分类中。 步骤一&#xff1a;选中商品 在个人中心点击管理入口&#xff0c;然后找到“商品管理”菜单并点击。找到需要添加的商品&#xff0c;然后选中它。…

【网络安全带你练爬虫-100练】第15练:模拟用户登录

目录 一、目标1&#xff1a;理清逻辑 二、目标2&#xff1a;将每一步用代码进行表示 三、网络安全O 一、目标1&#xff1a;理清逻辑 模拟登录的基本流程 1、进入入口程序 2、读取目标URL 3、请求加上线程 4、确定请求数据包 5、请求格式的确认 6、数据的处理与判断 二、目标…

MixFormerV2: Efficient Fully Transformer Tracking

摘要 基于变压器的跟踪器在标准基准测试上取得了很强的精度。然而&#xff0c;它们的效率仍然是在GPU和CPU平台上实际部署的一个障碍。在本文中&#xff0c;为了克服这一问题&#xff0c;我们提出了一个完全变压器跟踪框架&#xff0c;称为MixFormerV2&#xff0c;没有任何密集…

我的2023上半年总结

Hi~C站的小伙伴们好久不见哇&#xff01;釉色终于回到C站&#xff0c;开始要输出了&#xff01;这一篇文章是我的2023上半年的总结&#xff0c;以此&#xff0c;致敬那段迷茫但又不曾被辜负的时光。 文章目录 总括——你愿意花五分钟时间读读我的文章吗学习——制定目标&#…

GB/T 25000.51解读——软件产品的性能效率怎么测?

GB/T 25000.51-2016《软件产品质量要求和测试细则》是申请软件检测CNAS认可一定会用到的一部国家标准。在前面的文章中&#xff0c;我们为大家整体介绍了GB/T 25000.51-2016《软件产品质量要求和测试细则》国家标准的结构和所涵盖的内容以及对软件产品的八大质量特性中的功能性…

电机故障诊断(python程序,模型为CNN结合LSTM)

代码运行环境要求&#xff1a;TensorFlow版本>2.4.0&#xff0c;python版本>3.6.0 运行效果视频&#xff1a;电机故障诊断&#xff08;python代码&#xff09;_哔哩哔哩_bilibili 1.电机常见的故障类型有以下几种&#xff1a; 轴承故障&#xff1a;轴承是电机运转时最容…

新星计划打卡学习:VUE3引入element-plus

目录 1、安装element-plus 2、安装按需导入插件 3、修改配置文件 4、添加页面内容 5、保存并重启项目 1、安装element-plus 官网说要想使用element-plus需要先进行安装&#xff0c;并给出了三种安装方式&#xff0c;我选择了第三种。 报错了&#xff1a; 解决的办法&…