Why my method causes TLE?


  • 0
    R

    The following is my method. When I run code, it can show the correct answer, but when I submit my method, it always tells me TLE. The test case that I can not pass is "n = 8, k = 8950". But when I run code directly, it can shows the right answer and the time is 3ms. I want to know why. Please help me!

    public String getPermutation(int n, int k) {
            int[] nums = new int[n];
            for(int i = 0; i < n; i++){
                nums[i] = i+1;
            }
            
            for(int i = 1; i < k; i++)
                hasNextPer(nums);
            StringBuilder sb = new StringBuilder();
            for(int num : nums)
                sb.append(num);
            return sb.toString();
        }
        
        public void hasNextPer(int[] nums){
            int pos = -1;
            int len = nums.length;
            for(int i = len - 1; i > 0; i--){
                if(nums[i] > nums[i - 1]){
                    pos = i-1;
                    break;
                }
            }
            if(pos == -1)
                return;
            for(int i = len - 1; i > pos; i--){
                if(nums[i] > nums[pos]){
                    swap(nums,pos,i);
                    break;
                }
            }
            
            Arrays.sort(nums,pos+1,len);
        }
        
        public void swap(int[] nums, int pos, int i){
            nums[pos] ^= nums[i];
            nums[i] ^= nums[pos];
            nums[pos] ^= nums[i];
        }`enter code here`

  • 0
    M

    use k = k mod n! can make the first loop finished in n! times, but still LTE... Maybe try to find the next permutation is the wrong way.

    if k< n!, the first number will be 1.
    if n!<k<2n!, the first number will be 2.
    ...
    try this recursive method.


Log in to reply
 

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