当前位置: 首页 > news >正文

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)。如果大家还有什么不同的看法可以跟姜糖展开讨论哦。

相关文章:

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

目录 一、题目 二、分析 2.1 暴力求解法 2.2 找规律 2.3 追求时间效率&#xff0c;以空间换时间 三、结论 一、题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出…...

MySQL中CAST和CONVERT函数都用于数据类型转换

在 MySQL 中&#xff0c;CAST() 和 CONVERT() 函数都用于数据类型转换。虽然这两个函数在大多数情况下可以互换使用&#xff0c;但它们之间还是有一些细微的差别。 官方文档地址 https://dev.mysql.com/doc/refman/8.4/en/cast-functions.html#function_cast CAST() 函数 C…...

速盾:cdn影响seo吗?

CDN (Content Delivery Network) 是一个分布式网络架构&#xff0c;用于在全球范围内加速网站内容的传输和分发。它通过将网站的静态资源&#xff08;例如图片、CSS、JavaScript 文件等&#xff09;存储在多个服务器上&#xff0c;使用户可以从最接近他们位置的服务器上获取这些…...

期末算法复习

0-1背包问题&#xff08;动态规划&#xff09; 例题 算法思想&#xff1a; 动态规划的核心思想是将原问题拆分成若干个子问题&#xff0c;并利用已解决的子问题的解来求解更大规模的问题。 主要是状态转移方程和状态 算法描述&#xff1a; 初始化一个二维数组dp&#xff0…...

可穿戴设备:苹果“吃老底”、华为“忙复苏”、小米“再扩容”

配图来自Canva可画 随着产品功能的创新&#xff0c;可穿戴设备不再被简单地视为手机的延伸&#xff0c;而是被当成一种独立的、具有独特功能和优势的产品&#xff0c;受到了越来越多人的青睐。 一方面&#xff0c;技术的进步使得可穿戴设备在功能、性能和使用体验上得到显著提…...

AI数据分析:集中度分析和离散度分析

在deepseek中输入提示词&#xff1a; 你是一个Python编程专家&#xff0c;要完成一个Python脚本编写的任务&#xff0c;具体步骤如下&#xff1a; 读取Excel表格&#xff1a;"F:\AI自媒体内容\AI行业数据分析\toolify月榜\toolify2023年-2024年月排行榜汇总数据.xlsx&qu…...

redis的分布式session和本地的session有啥区别

在web应用开发中&#xff0c;Session用于在多个请求之间存储用户数据。传统上&#xff0c;Session存储在服务器的内存中&#xff0c;即本地Session。然而&#xff0c;随着应用规模和复杂度的增加&#xff0c;特别是在分布式环境中&#xff0c;本地Session会遇到一些问题。这时&…...

SSH概念、用途、详细使用方法

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…...

关于电脑文件的规划思考

概述 设置C、D、E、F 四个盘 C盘&#xff1a;系统数据使用&#xff0c;操作系统、其他软件需要用到的系统性资源 D盘&#xff1a;应用软件区 的使用&#xff0c;数据库、navacat、idea、visual studio、浏览器、向日葵、虚拟机…… E盘&#xff1a;工作区&#xff1a;公司资料…...

DVWA - Brute Force

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

安卓手机文件找回方法汇总,3个技巧,不再焦虑

我们用手机来储存各种重要的信息和文件&#xff0c;无论是珍贵的照片、重要的文档还是喜爱的音乐&#xff0c;用来记录和分享生活中的每一个瞬间。但如果不小心删除了这些文件&#xff0c;我们可能会面临数据丢失的风险&#xff0c;进而产生焦虑和不安。本文将为您揭秘手机文件…...

{}初始化

文章目录 ()初始化的问题易混淆弱检查 {}初始化{}初始化是c11推荐的初始化&#xff0c;解决了上述的问题 ()则被用于强制类型转换 ()初始化的问题 易混淆 string s();不能确定是函数定义还是对象定义 弱检查 int a(3.14);3.14 可以通过 int 定义 {}初始化 {}初始化是c11推…...

小程序外卖开发中的关键技术与实现方法

小程序外卖服务凭借其便捷性和灵活性&#xff0c;正成为现代餐饮行业的重要组成部分。开发一个功能完善的小程序外卖系统&#xff0c;需要掌握一系列关键技术和实现方法。本文将介绍小程序外卖开发中的核心技术&#xff0c;并提供具体的代码示例&#xff0c;帮助开发者理解和实…...

大数据平台之运维管理工具

大数据平台的自动化运维管理工具能够大幅提升集群管理效率&#xff0c;减少人为错误&#xff0c;提高系统的稳定性和性能。这些工具通常提供集群监控、配置管理、自动化任务执行、安全管理和故障处理等功能。以下是一些主要的大数据平台自动化运维管理工具的详细介绍&#xff1…...

[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图表&#xff0c;和记录信息的区域数据处理 07 删除功能&#xff0c;撤销功…...

python判断一个数是不是偶数

在Python中&#xff0c;你可以使用模运算符 % 来判断一个数是否为偶数。模运算符会返回两个数相除的余数。如果一个数除以2的余数为0&#xff0c;那么这个数就是偶数。 以下是一个简单的Python函数&#xff0c;用于判断一个数是否为偶数&#xff1a; def is_even(n):return n…...

Apipost模拟HTTP客户端

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

uniapp 调用手机上安装的app (高德地图 百度地图 Apple地图 谷歌地图)

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

如果供应商不能按时交货怎么办?

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

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

C++使用 new 来创建动态数组

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

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门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加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...