C语言王国——数组的旋转(轮转数组)三种解法

目录

一、题目

二、分析 

2.1 暴力求解法

2.2  找规律

2.3 追求时间效率,以空间换时间

三、结论 


一、题目

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:

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

示例 2:

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

二、分析 

2.1 暴力求解法

这题是旋转字符串但是它的实质是将前面n-1个数据往后移一位,然后将最后一个数据移到第一个,旋转几次则执行几次这个步骤。为了变量不被覆盖,变量采取从后向前移动,而最后一个数据利用一个空变量temp去拷贝一份,在前面数据移动完成后则拷贝到第一个数据。如下面代码:

void rotate(int* num ,int k , int size)
{k %= size;//size次一次循环while (k){int temp = num[size-1];for (int i = size-1; i > 0; i--){num[i] = num[i - 1];}num[0] = temp;k--;}
}int main()
{int arr[] = { 7,1,2,3,4,5,6 };int size = sizeof(arr) / sizeof(arr[0]);int k = 1;printf("旋转几次数组:");scanf("%d", &k);printf("旋转前:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}rotate(arr, k, size);printf("\n旋转后为:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}return 0;
}

2.2  找规律

我们发现暴力求解虽然可以解出此题,但是时间复杂度O(N^{2}),那我们有什么办法去降低时间复杂度呢?我们可以尝试降低它的循环次数,找找看他们有什么规律?

如图,将前面n-k个数字逆置然后将后面n个逆置,然后将他们整体逆置。(红色位将要进行逆置的数)

代码如下:

void Inversion(int* arr, int l, int r)
{while (l < r){int temp = arr[l];arr[l] = arr[r];arr[r] = temp;l++;r--;}
}void rotate(int* nums, int numsSize, int k) {k %= numsSize;//不让数组越界,完成一次数组长度的旋转数组不变Inversion(nums, 0, numsSize - k - 1);Inversion(nums, numsSize - k, numsSize - 1);Inversion(nums, 0, numsSize - 1);
}int main()
{int arr[] = { 7,1,2,3,4,5,6 };int size = sizeof(arr) / sizeof(arr[0]);int k = 1;printf("旋转几次数组:");scanf("%d", &k);printf("旋转前:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}rotate(arr, size, k);printf("\n旋转后为:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}return 0;
}

*这里要注意数组越界访问,我们发现数组完成一次数组长度的旋转,数组不变,所以我们取模于数组长度。 

2.3 追求时间效率,以空间换时间

这里我们不讨论空间复杂度只优化时间复杂度,所以我们可以新开辟一段空间,将后n个旋转的数字先放入我们开辟的空间,然后再将前面的n-k个数字放入空间后面。

如代码:

void rotate(int* nums, int numsSize, int k) {k %= numsSize;int* temp = (int*)malloc(sizeof(int) * numsSize);memcpy(temp, nums + numsSize - k, sizeof(int) * k);memcpy(temp + k, nums, sizeof(int) * (numsSize - k));memcpy(nums, temp, sizeof(int) * numsSize);free(temp);//释放临时空间temp = NULL;
}int main()
{int arr[] = { 7,1,2,3,4,5,6 };int size = sizeof(arr) / sizeof(arr[0]);int k = 1;printf("旋转几次数组:");scanf("%d", &k);printf("旋转前:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}rotate(arr, size, k);printf("\n旋转后为:");for (int i = 0; i < size; i++){printf("%d ", arr[i]);}return 0;
}

三、结论 

每一道题都有属于自己的空间和时间复杂度,当你写出一段代码的时候去想想还能不能继续去优化它,使它的时间和空间复杂度更小。姜糖在这里就是不断在优化它的时间复杂度,从O(N^2)到最后的O(N)。如果大家还有什么不同的看法可以跟姜糖展开讨论哦。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

树莓派4B_OpenCv学习笔记6:OpenCv识别已知颜色_运用掩膜

今日继续学习树莓派4B 4G&#xff1a;&#xff08;Raspberry Pi&#xff0c;简称RPi或RasPi&#xff09; 本人所用树莓派4B 装载的系统与版本如下: 版本可用命令 (lsb_release -a) 查询: Opencv 版本是4.5.1&#xff1a; 学了这些OpenCv的理论性知识&#xff0c;不进行实践实在…

数据库管理-第205期 换个角度看23ai(20240617)

数据库管理205期 2024-06-17 数据库管理-第205期 换个角度看23ai&#xff08;20240617&#xff09;1 规范应用开发2 融合总结 数据库管理-第205期 换个角度看23ai&#xff08;20240617&#xff09; 作者&#xff1a;胖头鱼的鱼缸&#xff08;尹海文&#xff09; Oracle ACE Pro…

11.5.k8s中pod的调度-cordon,drain,delete

目录 一、概念 二、使用 1.cordon 停止调度 1.1.停止调度 1.2.解除恢复 2.drain 驱逐节点 2.1.驱逐节点 2.2.参数介绍 2.3.解除恢复 3.delete 删除节点 一、概念 cordon节点&#xff0c;drain驱逐节点&#xff0c;delete 节点&#xff0c;在对k8s集群节点执行维护&am…

vivado NODE、PACKAGE_PIN

节点是Xilinx部件上用于路由连接或网络的设备对象。它是一个 WIRE集合&#xff0c;跨越多个瓦片&#xff0c;物理和电气 连接在一起。节点可以连接到单个SITE_&#xff0c; 而是简单地将NETs携带进、携带出或携带穿过站点。节点可以连接到 任何数量的PIP&#xff0c;并且也可以…

Science | 稀土开采威胁马来西亚的生物多样性

马来西亚是一个生物多样性热点地区&#xff0c;拥有超过17万种物种&#xff0c;其中1600多种处于濒临灭绝的风险。马来西亚的热带雨林蕴藏了大部分的生物多样性&#xff0c;并为全球提供重要的生态系统效益&#xff0c;同时为土著社区带来经济和文化价值。同时马来西亚具有可观…

04 远程访问及控制

1、SSH远程管理 SSH是一种安全通道协议&#xff0c;主要用来实现字符界面的远程登录、远程复制等功能。 SSH协议对通信双方的数据传输进行了加密处理&#xff08;包括用户登陆时输入得用户口令&#xff09;。 终端&#xff1a;接收用户的指令 TTY终端不能远程&#xff0c;它…

Python界面编辑器Tkinter布局助手 使用体验

一、发现 我今天在网上搜关于Python Tkinter方面的信息时&#xff0c;发现了Python界面编辑器 Tkinter布局助手 的使用说明。 https://blog.csdn.net/weixin_52777652/article/details/135291731?spm1001.2014.3001.5506 这个编辑器是个开源的项目&#xff0c;个人用户可以…

大模型KV Cache节省神器MLA学习笔记(包含推理时的矩阵吸收分析)

首先&#xff0c;本文回顾了MHA的计算方式以及KV Cache的原理&#xff0c;然后深入到了DeepSeek V2的MLA的原理介绍&#xff0c;同时对MLA节省的KV Cache比例做了详细的计算解读。接着&#xff0c;带着对原理的理解理清了HuggingFace MLA的全部实现&#xff0c;每行代码都去对应…

从中概回购潮,看互联网的未来

王兴的饭否语录里有这样一句话&#xff1a;“对未来越有信心&#xff0c;对现在越有耐心。” 而如今的美团&#xff0c;已经不再掩饰对未来的坚定信心。6月11日&#xff0c;美团在港交所公告&#xff0c;计划回购不超过20亿美元的B类普通股股份。 而自从港股一季度财报季结束…

【吉林大学Java程序设计】第9章:并发控制

第9章&#xff1a;并发控制 1.线程的基本概念2.线程的创建与启动3.线程的调度与优先级线程的状态线程的生命周期线程控制的基本方法线程优先级 4.线程的协作多线程存在的问题同步区域&#xff08;临界区&#xff09;生产者与消费者问题&#xff08;互斥与同步问题&#xff09;哲…

线程池吞掉异常的case:源码阅读与解决方法

1. 问题背景 有一天给同事CR&#xff0c;看到一段这样的代码 try {for (param : params) {//并发处理&#xff0c;func无返回值ThreadPool.submit(func(param));} } catch (Exception e) {log.info("func抛异常啦,参数是:{}", param) } 我&#xff1a;你这段代码是…

【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注 ​ 目录 一、问题描述 二、解题思路 方法一&#xff1a;数学公式推导法 方法…

苏州辰安塑业携塑料托盘、塑料物流箱解决方案亮相2024杭州快递物流展

苏州辰安塑业携塑料托盘、吹塑托盘、塑料卡板箱、塑料周转箱、塑料物流箱、塑料垃圾桶解决方案盛装亮相2024杭州快递物流展&#xff01; 展位号&#xff1a;3C馆A51 苏州辰安塑业有限公司&#xff0c;是一家专业从事塑料托盘、吹塑托盘、塑料卡板箱、塑料周转箱、塑料物流箱、…

【前端】Nesj 学习笔记

1、前置知识 1.1 装饰器 装饰器的类型 declare type ClassDecorator <TFunction extends Function>(target: TFunction) > TFunction | void; declare type PropertyDecorator (target: Object, propertyKey: string | symbol) > void; declare type MethodDe…

大模型应用开发技术:Multi-Agent框架流程、源码及案例实战(二)

LlaMA 3 系列博客 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;一&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;二&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;三&#xff09; 基于 LlaMA…

05-5.4.1 树的存储结构

&#x1f44b; Hi, I’m Beast Cheng &#x1f440; I’m interested in photography, hiking, landscape… &#x1f331; I’m currently learning python, javascript, kotlin… &#x1f4eb; How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…

经验分享,xps格式转成pdf格式

XPS 是一种电子文档格式、后台打印文件格式和页面描述语言。有时候微软默认打印机保存的是xps格式&#xff0c;我们如何转换为pdf格式呢&#xff0c;这里分享一个免费好用的网站&#xff0c;可以实现。 网站&#xff1a;https://xpstopdf.com/zh/ 截图&#xff1a;

JVM 三色标记算法

三色标记算法核心原理 三色标记算法是一种JVM的垃圾标记算法&#xff0c;CMS/G1垃圾回收器就是使用的这种算法&#xff0c;它可以让JVM在不发生或者尽可能短的发生STW&#xff08;Stop The World&#xff09;的情况下进行垃圾的标记和清除。 顾名思义&#xff0c;三色标记算法…

Linux(Centos7)OpenSSH漏洞修复,升级最新openssh-9.7p1

OpenSSH更新 一、OpenSSH漏洞二、安装zlib三、安装OpenSSL四、安装OpenSSH 一、OpenSSH漏洞 服务器被扫描出了漏洞需要修复&#xff0c;准备升级为最新openssh服务 1. 使用ssh -v查看本机ssh服务版本号 ssh -V虚拟机为OpenSSH7.4p1&#xff0c;现在准备升级为OpenSSH9.7p1…

springboot小型超市商品展销系统-计算机毕业设计源码01635

摘 要 科技进步的飞速发展引起人们日常生活的巨大变化&#xff0c;电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流&#xff0c;人类发展的历史正进入一个新时代。在现实运用中&#xff0c;应用软件的工作…