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 找规律
我们发现暴力求解虽然可以解出此题,但是时间复杂度,那我们有什么办法去降低时间复杂度呢?我们可以尝试降低它的循环次数,找找看他们有什么规律?
如图,将前面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)。如果大家还有什么不同的看法可以跟姜糖展开讨论哦。
相关文章:

C语言王国——数组的旋转(轮转数组)三种解法
目录 一、题目 二、分析 2.1 暴力求解法 2.2 找规律 2.3 追求时间效率,以空间换时间 三、结论 一、题目 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出…...
MySQL中CAST和CONVERT函数都用于数据类型转换
在 MySQL 中,CAST() 和 CONVERT() 函数都用于数据类型转换。虽然这两个函数在大多数情况下可以互换使用,但它们之间还是有一些细微的差别。 官方文档地址 https://dev.mysql.com/doc/refman/8.4/en/cast-functions.html#function_cast CAST() 函数 C…...
速盾:cdn影响seo吗?
CDN (Content Delivery Network) 是一个分布式网络架构,用于在全球范围内加速网站内容的传输和分发。它通过将网站的静态资源(例如图片、CSS、JavaScript 文件等)存储在多个服务器上,使用户可以从最接近他们位置的服务器上获取这些…...

期末算法复习
0-1背包问题(动态规划) 例题 算法思想: 动态规划的核心思想是将原问题拆分成若干个子问题,并利用已解决的子问题的解来求解更大规模的问题。 主要是状态转移方程和状态 算法描述: 初始化一个二维数组dp࿰…...

可穿戴设备:苹果“吃老底”、华为“忙复苏”、小米“再扩容”
配图来自Canva可画 随着产品功能的创新,可穿戴设备不再被简单地视为手机的延伸,而是被当成一种独立的、具有独特功能和优势的产品,受到了越来越多人的青睐。 一方面,技术的进步使得可穿戴设备在功能、性能和使用体验上得到显著提…...

AI数据分析:集中度分析和离散度分析
在deepseek中输入提示词: 你是一个Python编程专家,要完成一个Python脚本编写的任务,具体步骤如下: 读取Excel表格:"F:\AI自媒体内容\AI行业数据分析\toolify月榜\toolify2023年-2024年月排行榜汇总数据.xlsx&qu…...
redis的分布式session和本地的session有啥区别
在web应用开发中,Session用于在多个请求之间存储用户数据。传统上,Session存储在服务器的内存中,即本地Session。然而,随着应用规模和复杂度的增加,特别是在分布式环境中,本地Session会遇到一些问题。这时&…...

SSH概念、用途、详细使用方法
还是大剑师兰特:曾是美国某知名大学计算机专业研究生,现为航空航海领域高级前端工程师;CSDN知名博主,GIS领域优质创作者,深耕openlayers、leaflet、mapbox、cesium,canvas,webgl,ech…...

关于电脑文件的规划思考
概述 设置C、D、E、F 四个盘 C盘:系统数据使用,操作系统、其他软件需要用到的系统性资源 D盘:应用软件区 的使用,数据库、navacat、idea、visual studio、浏览器、向日葵、虚拟机…… E盘:工作区:公司资料…...

DVWA - Brute Force
DVWA - Brute Force 等级:low 直接上bp弱口令爆破,设置变量,攻击类型最后一个,payload为用户名、密码简单列表 直接run,长度排序下,不一样的就是正确的用户名和密码 另解: 看一下…...

安卓手机文件找回方法汇总,3个技巧,不再焦虑
我们用手机来储存各种重要的信息和文件,无论是珍贵的照片、重要的文档还是喜爱的音乐,用来记录和分享生活中的每一个瞬间。但如果不小心删除了这些文件,我们可能会面临数据丢失的风险,进而产生焦虑和不安。本文将为您揭秘手机文件…...
{}初始化
文章目录 ()初始化的问题易混淆弱检查 {}初始化{}初始化是c11推荐的初始化,解决了上述的问题 ()则被用于强制类型转换 ()初始化的问题 易混淆 string s();不能确定是函数定义还是对象定义 弱检查 int a(3.14);3.14 可以通过 int 定义 {}初始化 {}初始化是c11推…...

小程序外卖开发中的关键技术与实现方法
小程序外卖服务凭借其便捷性和灵活性,正成为现代餐饮行业的重要组成部分。开发一个功能完善的小程序外卖系统,需要掌握一系列关键技术和实现方法。本文将介绍小程序外卖开发中的核心技术,并提供具体的代码示例,帮助开发者理解和实…...
大数据平台之运维管理工具
大数据平台的自动化运维管理工具能够大幅提升集群管理效率,减少人为错误,提高系统的稳定性和性能。这些工具通常提供集群监控、配置管理、自动化任务执行、安全管理和故障处理等功能。以下是一些主要的大数据平台自动化运维管理工具的详细介绍࿱…...

[vue3]组件通信
自定义属性 父组件中给子组件绑定属性, 传递数据给子组件, 子组件通过props选项接收数据 props传递的数据, 在模版中可以直接使用{{ message }}, 在逻辑中使用props.message defineProps defineProps是编译器宏函数, 就是一个编译阶段的标识, 实际编译器解析时, 遇到后会进行…...

【react小项目】bmi-calculator
bmi-calculator 目录 bmi-calculator初始化项目01大致布局01代码 02完善样式02代码 03输入信息模块03代码 04 使用图表04代码 05详细记录信息渲染05代码 06 让数据变成响应式的06-1输入框的数据处理06-2图表,和记录信息的区域数据处理 07 删除功能,撤销功…...
python判断一个数是不是偶数
在Python中,你可以使用模运算符 % 来判断一个数是否为偶数。模运算符会返回两个数相除的余数。如果一个数除以2的余数为0,那么这个数就是偶数。 以下是一个简单的Python函数,用于判断一个数是否为偶数: def is_even(n):return n…...

Apipost模拟HTTP客户端
模拟HTTP客户端的软件有很多,其中比较著名的就有API-FOX、POSTMAN。 相信很多小伙伴都使用POSTMAN。这篇博客主要介绍Apipost的原因是,Apipost无需下载,具有网页版。 APIFOX的站内下载: Api-Fox,类似于PostMan的软件…...

uniapp 调用手机上安装的app (高德地图 百度地图 Apple地图 谷歌地图)
uniapp 调用手机上安装的app (高德地图 百度地图 Apple地图 谷歌地图) 效果 思路 获取手机类型(安卓/iOS)let platform uni.getSystemInfoSync().platform判断手机有没有安装需要的应用plus.runtime.isApplicationExist({action: ""}))打开应用 跳转过去plus.runt…...

如果供应商不能按时交货怎么办?
虽然说我们在采购的时候,我们会和供应商签订合同,合同上也会注明交期时间等一些必需的条件。 但是当供货商真的没有如期交货,或者交货拖延的时候,我们第一时间选择的是拿起法律武器来让对方承担违约责任吗? 显然,这选…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...