189. Rotate Array (reverse in parts)
easy
https://leetcode.com/problems/rotate-array/
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]
.
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Understand the question & example, to see if rotate to right/left
Complexity: time O(n) space O(1)
ex:
let a= [1,2,3,4,5,6,7]
k = 3.
k = 3.
- reverse all and get[7,6,5,4,3,2,1]
- reverse the elements from 0 to k-1(#k ele) [5,6,7,4,3,2,1]
- reverse the rest get[5,6,7,1,2,3,4]
public class Solution { public void rotate(int[] nums, int k) { k %= nums.length;//ensure k is legit index //1. reverse the whole(here is to the right,if to the left, do reverse all at bottom) reverse(nums,0,nums.length-1); //2. reverse from 0 to k-1,(#k elements) reverse(nums,0,k-1); //3. reverse the rest reverse(nums,k,nums.length-1); } public void reverse(int[] nums,int start,int end){ while(start<end){ int tmp = nums[end]; nums[end] = nums[start]; nums[start] = tmp; start++; end--; } } }
No comments:
Post a Comment