Tuesday, February 24, 2015

Rotate array

So how to do it in place? The answer is easy but tricky. Reverse the array 3 times. First reverse the whole array, second reverse (0, k - 1) and third reverse(k, n -1).
Take a look of the example.




public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0 || k == nums.length)
            return;
        int l = nums.length;
        k = k % l;
        reverse(nums, 0, l - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, l - 1);
        
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

No comments:

Post a Comment