RotateArray

fishercoder1534 · fishercoder1534 · commit 1948ab100d71 · 2016-10-14T22:22:59.000-07:00
diff --git a/EASY/src/easy/RotateArray.java b/EASY/src/easy/RotateArray.java
@@ -0,0 +1,59 @@
+package easy;
+import java.util.*;
+
+/**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].*/
+public class RotateArray {
+
+    
+    /**My original idea and got AC'ed.
+     * One thing to notice is that when k > nums.length, we'll continue to rotate the array, it just becomes k -= nums.length
+     * 
+     * TODO: look at its Editorial Solution and use O(1) approach to redo it.*/
+    public static void rotate(int[] nums, int k) {
+        if(k == 0 || k == nums.length) return;
+        if(k > nums.length) k -= nums.length;
+        List<Integer> tmp = new ArrayList();
+        int i = 0;
+        if(nums.length-k >= 0){
+            i = nums.length-k;
+            for(; i < nums.length; i++){
+                tmp.add(nums[i]);
+            }
+        } else {
+            i = nums.length-1;
+            for(; i >= 0; i--){
+                tmp.add(nums[i]);
+            }
+
+        }
+        for(i = 0; i < nums.length-k; i++){
+            tmp.add(nums[i]);
+        }
+        for(i = 0; i < tmp.size(); i++){
+            nums[i] = tmp.get(i);
+        }
+    }
+    
+    public static void main(String...strings){
+//        int k = 1;
+//        int[] nums = new int[]{1,2,3};
+//        int[] nums = new int[]{1};
+//        int[] nums = new int[]{1,2};
+        
+//        int k = 3;
+//        int[] nums = new int[]{1,2};
+        
+//        int k = 2;
+//        int[] nums = new int[]{1,2};
+        
+        int k = 4;
+        int[] nums = new int[]{1,2,3};
+        
+//        int k = 2;
+//        int[] nums = new int[]{-1};
+        rotate(nums, k);
+    }
+
+}
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@
 |209|[Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)|[Solution](../../blob/master/MEDIUM/src/medium/MinimumSizeSubarraySum.java)| O(n)|O(1) | Medium|
 |206|[Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)|[Solution](../../blob/master/EASY/src/easy/ReverseLinkedList.java)| O(n)|O(1) | Easy
 |200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Union Find](../../blob/master/MEDIUM/src/medium/NumberOfIslandsUnionFind.java) [DFS](../../blob/master/MEDIUM/src/medium/NumberofIslandsDFS.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
+|189|[Rotate Array](https://leetcode.com/problems/rotate-array/)|[Solution](../../blob/master/EASY/src/easy/RotateArray.java)| O(n)|O(n), could be optimized to O(1) | Easy
 |173|[Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)|[Queue](../../blob/master/MEDIUM/src/medium/BSTIterator_using_q.java) [Stack](../../blob/master/MEDIUM/src/medium/BSTIterator_using_stack.java)| O(1) |O(h) | Medium|
 |140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../blob/master/HARD/src/hard/WordBreakII.java)| ? |O(n^2) | Hard| Backtracking/DFS
 |139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../blob/master/MEDIUM/src/medium/WordBreak.java)| O(n^2)|O(n) | Medium| DP
