2 solutions - java


  • 1
    M
    public class Solution {
        public void rotate(int[] nums, int k) {
    //      rotate_1(nums,k);
            rotate_2(nums,k);
        }
        //need O(n) space, copy and refill
        public void rotate_1(int[] nums, int k){
            if(nums==null || nums.length<2) return;
            final int N = nums.length;
            int[] temp = nums.clone();
            int mid = N-k%N;
            int index = 0;
            for(int i=mid; i<N; i++, index++){
                nums[index] = temp[i];
            }
            for(int i=0; i<mid; i++, index++){
                nums[index] = temp[i];
            }
        }
        // O(1) space, reverse 3 times.
        public void rotate_2(int[] nums, int k){
            if(nums==null || nums.length<2) return;
            final int N = nums.length;
            k = k%N;
            if(k==0) return;
            reverse(nums, 0, N-1);
            reverse(nums, 0, k-1);
            reverse(nums, k, N-1);
        }
        private void reverse(int[] nums, int start, int end){
            int temp;
            while(start<end){
                temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                end--;
            }
        }
    }
    

Log in to reply
 

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