[算法]Rotate Array
You may have been using Java for a while. Do you think a simple Java array question can be a challenge? Let's use the following problem to test.
Problem: 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]. How many different ways do you know to solve this problem?
Solution 1 - Intermediate Array
In a straightforward way, we can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy()
.
public void rotate(int[] nums, int k) {if(k > nums.length)k=k%nums.length;int[] result = new int[nums.length];for(int i=0; i < k; i++){result[i] = nums[nums.length-k+i];}int j=0;for(int i=k; i<nums.length; i++){result[i] = nums[j];j++;}System.arraycopy( result, 0, nums, 0, nums.length );}
Space is O(n) and time is O(n). You can check out the difference between System.arraycopy() and Arrays.copyOf().
Solution 2 - Bubble Rotate
Can we do this in O(1) space?
This solution is like a bubble sort.
public static void rotate(int[] arr, int order) {if (arr == null || order < 0) {throw new IllegalArgumentException("Illegal argument!");}for (int i = 0; i < order; i++) {for (int j = arr.length - 1; j > 0; j--) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}
However, the time is O(n*k).
Solution 3 – Reversal
Can we do this in O(1) space and in O(n) time? The following solution does.
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, 62. Rotate first part: 4,3,2,1,5,63. Rotate second part: 4,3,2,1,6,54. Rotate the whole array: 5,6,1,2,3,4
public static void rotate(int[] arr, int order) {order = order % arr.length;if (arr == null || order < 0) {throw new IllegalArgumentException("Illegal argument!");}//length of first partint a = arr.length - order;reverse(arr, 0, a-1);reverse(arr, a, arr.length-1);reverse(arr, 0, arr.length-1);}public static void reverse(int[] arr, int left, int right){if(arr == null || arr.length == 1)return;while(left < right){int temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
最新文章
- C/C++ char a[ ] 和 char *a 的差别,改变 char *a爆内存错误的原因
- uploadify上传错误:uncaught exception: call to startUpload failed原因
- 如何撤销 PhpStorm/Clion 等 JetBrains 产品的 “Mark as Plain Text” 操作 ?
- Spark集群 + Akka + Kafka + Scala 开发(4) : 开发一个Kafka + Spark的应用
- Win7 64位下sql server链接oracle的方法
- ThinkPHP 3.2.2 在 volist 多重循环嵌套中使用 if 判断标签
- 【转】PHP error_reporting() 错误控制函数功能详解
- Bluetooth in Android 4.2 and 4.3(三):Enable Bluetooth
- FTA
- 12个CSS高级技巧汇总
- pageoffice razor pageofficelink方式调用js实现操作文档
- IDL 遍历 XML文档示例
- Python知识目录
- python基础——1、python背景及特点——(YZ)
- mysql定时任务用到存储过程和定时任务
- PID控制器开发笔记之八:带死区的PID控制器的实现
- 转 node.js和 android中java加密解密一致性问题;
- RabbitMQ随笔
- .NET Core开发日志——从ASP.NET Core Module到KestrelServer
- TTL特殊门电路
热门文章
- sql server 集群配置
- Atitit.rust语言特性&#160;attilax&#160;总结
- hbase和mapreduce开发 WordCount
- C# SqlBulkCopy类批量导入数据
- 篇二、理解Android Studio的视图和目录分析,这个是转载
- 下载某资源文件并加载其中的所有Prefab到场景中
- iOS流布局UICollectionView系列七——三维中的球型布局
- Keepalived 集群在Linux下的搭建
- Entity Framework(1)——Connections and Models
- 【BZOJ1038】[ZJOI2008]瞭望塔 半平面交