Thursday, August 27, 2015

Leetcode: 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.
Code (Java):
public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return;
        }
        
        // Step 1: swap each element of the array
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        k %= nums.length; 
        
        // Step 2: swap the first k elements
        i = 0;
        j = k - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        // Step 3: swap the rest of k elements
        i = k;
        j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}


No comments:

Post a Comment