leecode 旋转数组
2024-10-20 03:21:20
描述
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入:[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:
输入:[-1,-100,3,99]
和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
- 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的原地算法。
解题思路:
解题思路有很多种,下面讲述两种比较巧妙的解法:
1.使用原地替换的方法,首先使用tmp记录数组第一个值,从第一个元素开始,不断的swap(tmp,nums[i]),其中i是tmp值的目标位置;这里要注意的一个情况就是移动的步数k是数组长度的因子,这样会出现重复循环的情况,需要一个标志位来标识这种情况从而打破循环;
void rotate(vector<int>& nums, int k) { if(nums.empty())
{
return;
} k %= nums.size(); int len = nums.size();
int c = len;
int tmp = nums[];
int i=;
int mark = i;
while(c-- >= )
{
i = (i + k) >= len ? i + k - len : i+k;
swap(nums[i],tmp);
if(c > && i == mark)
{
++i;
tmp = nums[i];
mark = i;
}
}
}
2.通过观察目标数组可以发现,目标数组的前k位是原数组的最后n-k位,所以通过反转数组实现,首先反转前n-k个元素,再反转后k个元素,最后反转整个数组实现。
Solution {
void rotate(vector<int>& nums, int k) { if(nums.empty())
{
return;
} int len = nums.size();
if(k % len == )
{
return;
} k %= len;
reverse(nums,,len - k - );
reverse(nums,len -k,len - );
reverse(nums,,len-);
} void reverse(vector<int>& nums,int start,int end)
{
while(start < end)
{
swap(nums[start],nums[end]);
++start;
--end;
}
}
};
最新文章
- React Native知识9-ScrollView组件
- SageCRM 快速获取连接中的SID的方法
- XVI Open Cup named after E.V. Pankratiev. GP of Eurasia
- Configure the max limit for concurrent TCP connections(转)
- XSHELL使用隧道
- 【Matplotlib】 标注细节注意
- jvm内存GC详解
- nginx简单双机热备:backup参数的使用
- Webbrowser中模拟连接点击(非鼠标模拟)
- Qt计算器开发(二):信号槽实现数学表达式合法性检查
- java自动生成略缩图
- Access中的自定义排序设置方式
- Java restful web service 开发入门
- JAVA PERSISTENCE API (JPA)
- Python 爬虫基础Selenium
- Python文件读取常用方法
- Excel删除重复值
- [记录] Mysql 复制表格结构
- U3D Invoke系列函数
- [Android Pro] 开发一流的 Android SDK:Fabric SDK 的创建经验
热门文章
- 爬虫库之BeautifulSoup学习(二)
- Introduction to Multi-Threaded, Multi-Core and Parallel Programming concepts
- 技术胖Flutter第四季-19导航父子页面的跳转返回
- java 多线程,sleep()和wait()
- IE8 以上版本兼容
- POJ - 3278 Catch That Cow BFS求线性双向最短路径
- CentOS 6.5 升级gcc到4.8 以及libstdc++
- [Xcode 实际操作]八、网络与多线程-(20)时间控件Timer定时功能
- SpringBoot 2.0 整合sharding-jdbc中间件,实现数据分库分表
- JavaScript简介和发展史,JavaScript组成和开发工具-乐字节