n = 7 (array size)and k =3(rotate right steps)
a= [1,2,3,4,5,6,7]
becomes
1 step, a=[7, 1,2,3,4,5,6] (shifted 7 to the leftmost)
2 steps, a= [6,7, 1,2,3,4,5] (shifted 6 to the leftmost)
3 steps, a =[5,6,7, 1,2,3,4] (shifted 5 to the leftmost)
Thought 1: shift one element to the leftmost at a time,
Q1: how to shift to the leftmost?
A1:keep swapping backward from the end of the array
Time would be O(k*n), space would be O(1)
Thought2: a =[5,6,7, 1,2,3,4], create a new array and assign the first three element from the end of the input array one by one until k (length to length-k+1) and assign the rest from the start of array (0 to length-K)
Time is O(n) for over all array, Space is O(n) for a new array
Thought3: Reverse technique, taking 3 reverse
Q1: what is reverse and how?
A1: [1,2,3] => [3,2,1] or [4,100,120,5]=>[5,100,120,4] and use swap between the first and the last
so rotate need 3 reverse
E.g., a= [1,2,3,4,5,6,7]
1st reverse idx 0 to n-k-1 [4,3,2,1 5,6,7]
2st reverse idx n-k to n-1 [4,3,2,1 7,6,5]
3st reverse idx 0 to n-1 [5,6,7,1,2,3,4]
Time:(3*n) , Space:O(1)
2. Implementation
// NOTE: k value
// NOTE: overwrite the original array [in-place array overwrite]
// NOTE: validate the input of reverse
// Time:O(k*n), Space:O(1) public void rotate (int[] nums, int k) { // valid the input if ( nums== null || nums.length==0 ) { throw new IllegaArgumentException("IllegalArgument"); } // NOTE: k value if ( k > nums.length) { k = k%nums.length; } if ( k == 0 ) { return; } for (int i = 0 ; i < k ; i ++) { // NOTE: i >0 since j-1 for (int j = nums.length -1 ;i>0; i--) { int temp = nums[j]; nums[j] = nums[j-1]; nums[j-1] = temp; } } }
// Time:O(n) over array, Space:O(n) new array public void rotate (int[] nums, int k) { // valid the input if (nums == null || nums.length = 0) { throw new IllegalArgumentException("Illegal Argument"); } if ( k > nums.length > 0) { k = k% nums.length; } if ( k == 0 ) { return; } int[] res = new int[nums.length]; for (int i = 0 ; i < k ; i ++) { res[i] = nums[nums.length-k + i];// start from rotate element 1 } for (int i = k ; i < res.length;i++) { res[i] = nums[i - k]; } // NOTE: overwrite the original array [in-place array overwrite] System.arraycopy(res, 0, nums,0, nums.length); }
// Time:O(n), Space:O(1) public void rotate(int[] nums, int k) { if (nums == null || nums.length == 0) { throw new IllegalArgumentException("illegal Argument"); } if (k > nums.length ) { k = k% nums.length; } if (k ==0 ) { return; } reverse(nums, 0, nums.length-k-1);// length-k is rotate start reverse(nums, nums.length -k, nums.length-1); reverse(nums, 0, nums.length-1); } public void reverse(int[] nums, int l, int r) { // NOTE: validate the input of reverse if (nums == null || nums.length ==1 ) { return; } while (l < r) { int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; l++; r--; } }3. Similar Ones
(M) Rotate List
(M) Reverse Words in a String II
[LinkedList] Reverse Linked List
No comments:
Post a Comment