Tuesday, January 17, 2017

Leetcode/微软Bloomberg -- 189. Rotate Array (reverse in parts)


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.

思路: reverse array by 3 parts (0 to end),(0 to k-1),(k to end).
           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.
  1. reverse all and get[7,6,5,4,3,2,1]
  2. reverse the elements from 0 to k-1(#k ele) [5,6,7,4,3,2,1]
  3. 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