当前位置:网站首页>leetcode每日一练:旋转数组
leetcode每日一练:旋转数组
2022-07-05 17:17:00 【利刃Cc】
链接: 旋转数组
要求我们转一次,就是把最后面的数移到最前面来,然后其他数字保持顺序往后移动一步。
常规思路: 就是用while循环,题目要求我们轮转n次,我们就将后n个数字分别移到最前面去。这种思路虽然行得通,但是仔细想,每次将前面的数字向后移,这个时间复杂度是不低的,所以我们这里不讲这种常规思路。
新思路: 题目要我们轮转数组,其实我们可以先将整个数组翻转顺序,然后再将前n - 1个数翻转顺序,最后将后numsSize - n个数翻转顺序(假设这里数组个数为numsSize个),其实就完成了数组轮转。
注:这里有一个关键的点,就是如果翻转n次,而n等于数组的长度numsSize的话,其实就是原数组不动,以此类推,所以我们可以对n进行一下处理。
而且这种思路的空间复杂度是O(1)的!
代码:
void partRotate(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){
k %= numsSize;
//若k模完长度为0,则无需轮转
if(k == 0)
return;
partRotate(nums, 0, numsSize - 1);//先翻转整个数组
partRotate(nums, 0, k - 1);//然后翻转前k - 1个
partRotate(nums, k, numsSize - 1);//最后翻转后numsSize - k个
}
边栏推荐
- 菜刀,蚁剑,冰蝎,哥斯拉的流量特征
- VBA驱动SAP GUI实现办公自动化(二):判断元素是否存在
- Tips for extracting JSON fields from MySQL
- MySql 查询符合条件的最新数据行
- 为什么阳历中平年二月是28天
- 如何保存训练好的神经网络模型(pytorch版本)
- What are the precautions for MySQL group by
- Knowing that his daughter was molested, the 35 year old man beat the other party to minor injury level 2, and the court decided not to sue
- 域名解析,反向域名解析nbtstat
- Is it safe for China Galaxy Securities to open an account? How long can I buy stocks after opening an account
猜你喜欢
URP下Alpha从Gamma空间到Linner空间转换(二)——多Alpha贴图叠加
7 pratiques devops pour améliorer la performance des applications
Use of ThinkPHP template
网络威胁分析师应该具备的十种能力
Winedt common shortcut key modify shortcut key latex compile button
In depth understanding of redis memory obsolescence strategy
Design of electronic clock based on 51 single chip microcomputer
mongodb(快速上手)(一)
How to write a full score project document | acquisition technology
一文了解MySQL事务隔离级别
随机推荐
mysql中取出json字段的小技巧
Cartoon: looking for the best time to buy and sell stocks
The comprehensive competitiveness of Huawei cloud native containers ranks first in China!
云安全日报220705:红帽PHP解释器发现执行任意代码漏洞,需要尽快升级
机器学习02:模型评估
Count the running time of PHP program and set the maximum running time of PHP
解决“双击pdf文件,弹出”请安装evernote程序
Sentinel-流量防卫兵
Independent development is a way out for programmers
一文了解Go语言中的函数与方法的用法
How to save the trained neural network model (pytorch version)
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
中国银河证券开户安全吗 开户后多久能买股票
MySQL queries the latest qualified data rows
蚂蚁金服的暴富还未开始,Zoom的神话却仍在继续!
Machine learning 02: model evaluation
CVPR 2022最佳学生论文:单张图像估计物体在3D空间中的位姿估计
Short the command line via jar manifest or via a classpath file and rerun
Customize the theme of matrix (I) night mode
查看自己电脑连接过的WiFi密码