mercredi 1 juillet 2015

Java Rotate an Array

I have the following problem to test:

Rotate an array of n elements to the right by k steps. For instance, with n = 5 and k = 2, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?

My solution in intermediate array: With Space is O(n) and time is O(n), I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy().

public void rotate(int[] nums, int k) {
    if(k > nums.length) 
        k=k%nums.length;

    int[] result = new int[nums.length];

    for(int i=0; i < k; i++){
        result[i] = nums[nums.length-k+i];
    }

    int j=0;
    for(int i=k; i<nums.length; i++){
        result[i] = nums[j];
        j++;
    }

    System.arraycopy( result, 0, nums, 0, nums.length );
}

But there is better way we can do it with bubble rotate(like bubble sort) in O(1) space ?

Aucun commentaire:

Enregistrer un commentaire