Rotate Array 解答
2024-10-14 03:55:56
Question
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7]
is rotated to [5,6,7,1,2,3,4]
.
Solution 1 Bubble Rotate
Similar with bubble sort, time complexity O(k * n), space cost O(1)
public class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
if (k >= length)
k = k % length;
if (k == 0)
return;
for (int i = 0; i < k; i++) {
for (int j = length - 1; j > 0; j--) {
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
}
}
}
}
Solution 2 Traverse
Key to this solution is to make a copy of original array. Time complexity O(n), space cost O(n).
Solution 3 Reversal
Assuming we are given {1,2,3,4,5,6} and order 2. The basic idea is:
1. Divide the array two parts: 1,2,3,4 and 5, 6
2. Rotate first part: 4,3,2,1,5,6
3. Rotate second part: 4,3,2,1,6,5
4. Rotate the whole array: 5,6,1,2,3,4
Time complexity O(n), space cost O(n)
public class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
if (k >= length)
k = k % length;
if (k == 0)
return;
reverse(nums, 0, length - k - 1);
reverse(nums, length - k, length - 1);
reverse(nums, 0, length - 1);
}
private void reverse(int[] nums, int start, int end) {
if (start == end || nums.length == 1)
return;
while (start < end) {
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start++;
end--;
}
}
}
最新文章
- linux通过挂载系统光盘搭建本地yum仓库的方法
- 转:SqlServer2012自增列值突然增大1000的原因及解决方法
- SQL Server2005主从复制实现
- EntityFramework 6.1.2-beta2
- 自学 iOS – 三十天三十个 Swift 项目
- LinuxC语言读取文件,分割字符串,存入链表,放入另一个文件
- HDU 4832 Chess(DP+组合数学)(2014年百度之星程序设计大赛 - 初赛(第二轮))
- 小韦系统装工行网银U盾驱动的方法
- pthread_cond_timedwait时间设置
- Codeforces Round #310 (Div. 2) A. Case of the Zeros and Ones 水题
- 两种方式连接mysql
- Codevs_1403_新三国争霸_(Kruskal+动态规划)
- 15个网页设计必备的Google Chrome 扩展
- JAVA小知识点-Finally和Return的执行关系
- C#入门经典-第15章ListBox,CheckedListBox
- javascript痛点之二作用域链
- win7 64 位操作系统,进程System,PID为4,扫描连接局域网ip地址的139和445端口
- ACM-ICPC 2018 沈阳赛区网络预赛-I模拟题啊!!!
- MySQL变量变更小记
- 修改VS2017模板文件,添加文件头部自定义注释