LeetCode Array Easy 189. Rotate Array
2024-10-07 18:45:21
---恢复内容开始---
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
问题描述:给定一个长度为n的数组和一个非负整数k,向右旋转k部。
思路,首先这里k是可以大于数组的长度的。我采用最暴力的解法,这种解法效率很低,提交之后只能到13%-85% 效率不固定
public void Rotate(int[] nums, int k) {
k = k % nums.Length;
int[] temp = new int[k];
if(k== nums.Length)
return;
int length = nums.Length;
for(int i = ; i < k; i++)
temp[i] = nums[length - k + i];
for(int i = length - k -; i >=; i--)
nums[i+k]=nums[i];
for(int i = ; i < k; i++)
nums[i]=temp[i];
}
解法二 采用反转的方式,先把所有的数组反转,然后反转前k个元素,再反转后n-k个元素
public class Solution {
public void Rotate(int[] nums, int k) {
k = k % nums.Length;
Reverse(nums, , nums.Length-);
Reverse(nums, , k-);
Reverse(nums, k, nums.Length-);
}
private void Reverse(int[] arr, int start, int end){
while(start < end){
int temp = arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}
}
但是 实测发现,后一种方法效率还不如第一种方法。
最新文章
- 让低版本的 Android 项目显示出 Material 风格的点击效果
- HTML-meta
- HTML 表单总结http://images2015.cnblogs.com/blog/1001203/201607/1001203-20160730200559841-2144892373.png
- 预定义的类型“Microsoft.CSharp.RuntimeBinder.Binder”未定义或未导入
- HDU 4864 (2014 Multi-University Training Contest 1 )
- expunge
- spring常用的连接池属性文件配置
- 20151209jquery学习笔记Ajax 代码备份
- linux case 语句
- 数学之路-python计算实战(2)-初遇pypy
- 每天一个linux命令(37)--iostat命令
- nohup和&;后台运行,查看占用端口进程
- nodeJS里面的模块
- [USACO16OPEN]关闭农场Closing the Farm_Silver
- Linux之解决你的网络问题
- python数据抓取分析(python + mongodb)
- Java学习笔记之——内部类
- 洛谷P4438 [HNOI/AHOI2018]道路(dp)
- shp与json互转(转载)
- 对nginx进行平滑升级