Why my code appears Time Limit Exceeded? this is my code.. anyone can tell me why? thanks..


  • 0
    I
    public void rotate(int[] nums, int k) {
            if(k==1){
                return ;
            }
            for(int i=0;i<k;i++){
                moveToRight(nums);
            }
        }
        private void moveToRight(int[] nums){
            int last = nums[nums.length-1];
            for(int i=0;i<nums.length-1;i++){
                nums[i+1] = nums[i];
            }
            nums[0] = last;
        }

  • 0
    H

    your solution looks o(n2), but the better one should be o(n)


  • 0
    Y

    I have the same problem too using this method. I think you can try. int time = k % nums.length; but It's also TLE...


  • 0
    N

    your algorithm run in the complexity of O(k*nums.length). you moved the whole nums array in every step. It cause too much overhead.


  • 0
    J

    there is no assumption written that k must be less than array length.
    so there is the situation where k is much greater than length with times.

    example:
    nums = {1,2,3,4,5,6,7}
    k = 70000000000;
    

    in fact, the ouput is the same, each number will be moved to the original position.
    but T(n) of your solution is O(k * length), so it will exceed time limitation in that test case.

    you should replace k = k % length with k


  • 0
    I

    yes! I've been aware of this problem,thank you !


  • 0
    I

    yeah... i understand your mind , i tryed your code with k = k % nums.length , but it still appears exceed time limitation...


  • 0
    J

    yes, it should have caused the TLE, since T(n) of your solution is O(k*n), when k is asymptotically to n, we get O(n2). It means it will cause TLE even for the case where
    k is equal to n -1 , usual case.
    In another way, your solution is not correct in this issue.
    you should struggle to finger out the solution with T(n) = O(n).


  • 0
    I

    OK, i will struggle to finger out my problem... thanks very much...


Log in to reply
 

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