当前位置: 首页 > 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;这选…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

虚幻基础:角色旋转

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 移动组件使用控制器所需旋转&#xff1a;组件 使用 控制器旋转将旋转朝向运动&#xff1a;组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转&#xff1a;必须移动才能旋转&#xff0c;不移动不旋转控制器…...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...

Ubuntu 安装 Mysql 数据库

首先更新apt-get工具&#xff0c;执行命令如下&#xff1a; apt-get upgrade安装Mysql&#xff0c;执行如下命令&#xff1a; apt-get install mysql-server 开启Mysql 服务&#xff0c;执行命令如下&#xff1a; service mysql start并确认是否成功开启mysql,执行命令如下&am…...