My answer to this problem using java, passed all the test. Do you guys have any ideas to improve this answer?


  • 0
    H

    public class Solution {
    public void rotate(int[] nums, int k) {
    int length;
    length = nums.length;

        int a[] = new int[length];
        if(length==1)
        {
            for(int i = 0; i< length; i++)
            {
                nums[i]=nums[i];
            }
        }
        else if(length<k)
        {
            k=k%length;
            ArrayList<Integer> blist=new ArrayList<Integer>(length);
            
            for(int i =length-k; i<length;i++)
            {
                blist.add(nums[i]);
            }
            
            for(int i = 0; i<(length-k);i++)
            {
                blist.add(nums[i]);
            }
            for(int i = 0; i< length; i++)
            {
                nums[i]=blist.get(i);
            }
        }
        else
        {
        	ArrayList<Integer> blist=new ArrayList<Integer>(length);
            
            for(int i =Math.abs(length-k); i<length;i++)
            {
                blist.add(nums[i]);
            }
            
            for(int i = 0; i<(length-k);i++)
            {
                blist.add(nums[i]);
            }
            for(int i = 0; i< length; i++)
            {
                nums[i]=blist.get(i);
            }
        }
        
        
    }
    

    }


  • 0
    S
    This post is deleted!

  • 0
    S

    Well, your algorithm is using extra O(n) space.

    There is a lot to improve. Try to think it O(1).

    I read through the Discuss and find three ways to do it O(1). I'll just mention the core part to leave you thinking about it.

    1. do total swap three times. total swap means [1 2 3] -> [3 2 1]

    2. finding the correct one for a position, and then find the correct one for the position just being found.

    3. swap as much you as can, leave the rest to a recursive call.


  • 0
    C

    recursive calls always use extra space, so it won't be O(1) space


  • 0
    I

    Here is my Java solution. It is straight forward but not so smart. Still trying to figure out the O(1) space solution.

    public class Solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        int[] res = nums.clone();
        if(k%len == 0){
            return;
        }
        int ktail = k%len;
        for(int i=len-ktail, j=0;i<len;i++,j++){
            res[j] = nums[i];
        }
        for(int j=ktail, i=0;j<len;i++,j++){
            res[j] = nums[i];
        }
        System.arraycopy( res, 0, nums, 0, len );
    }
    

    }


  • 0
    S

    Recursive calls for stack structured algorithm is always use extra space. However, a queue structure recursive method is not using extra space.


  • 0
    D

    I think the best way is the three reverse method, outlined here: http://leetcode.com/2010/04/rotating-array-in-place.html

    This method is O(n) time and O(1) space, and it's the easiest/cleanest/most elegant way to code it in an interview.

    Here's my accepted Java code using this method:

     public class Solution {
        public void rotate(int[] nums, int k) {
            if (k == 0) return;
            
            k = k % nums.length;
             
            reverse(nums, 0, nums.length-1);
            reverse(nums, 0, k-1);
            reverse(nums, k, nums.length-1);
            
        }
        
        public void reverse(int[] arr, int i, int j){
            while (i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
    }
    

  • 0
    T

    Can you explain how this code works? I see that it does work, but I am interested in the concept behind it, why are we running reverse three times?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.