4 kinds of solution with brief analysis


  • 0
    J

    1.Use auxiliary storage to improve the run time. Core idea is to copy the first k elements of result array from original array, then put the first n -k elements to the tail of array.T(n) = O(n+k) , beats 13 % java submission. Not so good. As well it is with S(n) = O(n).

    Solution 1

    public void rotate(int[] nums, int k) {    
            k = k % nums.length; 
            int[] tmp = new int[k];
            for (int i = 0; i< k; i++){
                tmp[i] = nums[nums.length-k+i];
            }
            for (int i = nums.length-k-1 ; i >= 0;i--){
                nums[i+k] = nums[i];
            }
            for (int i = 0; i < tmp.length ; i ++){
                nums[i] = tmp[i];
            }
    
    }
    

    2.Use system.arraycopy to improve the performance. The core idea is the same with solution 1. It beats 95 % submission. However, Space (n) = O(n)

    public void rotate(int[] nums, int k) {	   
                k = k % nums.length;
    	        int[] tmp = new int [nums.length];
    	        System.arraycopy(nums, nums.length - k, tmp, 0, k);
    	        System.arraycopy(nums, 0, tmp, k, nums.length - k);
    	        System.arraycopy(tmp, 0, nums, 0, nums.length);               
     }
    

    3.Use Mod to find the new position, new index = (old index + k)%n.
    T(n) = O(2n) when n <<< k, solution 3 is greater than solution 1. Beats 13.8% not so good

    public void rotate(int[] nums, int k) {	     
            int[] tmp = new int[nums.length];
            for (int i = 0 ; i < nums.length; i++){
                tmp[i] = nums[i];
            }
            for (int i = 0 ; i< nums.length;i++){
                int index = (i+k)%nums.length;
                nums[index] = tmp[i];
            }
    }
    

    4.With S(n) = O(1) extra storage, use the core idea that is a[(i+k) % length] = a[i] recursively, use the extra storage to keep the temp value. Be caution is that the recursion will be dead loop when the tail meet the head, so I use a boolean value to indicate the first meet.So the T(n) = O(n), beats the 14 % submission, but with least extra storage, which of others is S(n) = O(n)

    public static void rotate(int[] nums, int k) {
        int index = 0;
        k = k % nums.length;
        int startIndex = 0; // move to right when loop recursively
        int tmp = nums[index]; //keep the first value 
        int tmmp = 0; // used as the temporary value when swap with tmp
        int i = 0; // sum number of finding new index, sum is equal to length
        while (i < nums.length){
            //first time of index = startIndex, indicating loop when meet twice
            boolean isFirst = true;
            index = startIndex; // init index
            tmp = nums[index];
            while (index != startIndex || isFirst ){
                index = (index + k) % nums.length;
                tmmp = nums[index];
                nums[index] = tmp;
                tmp = tmmp;
                isFirst = false;
                i++;
            }
            startIndex ++;
        }

Log in to reply
 

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