A 3ms LinkedList O(n2) Solution


  • 0
    L
    //while it's not faster than char array solution.
    
    public class Solution {
        //123 3
        public String getPermutation(int n, int k) {
            if(k < 1) return "";
            int[] frac = new int[n + 1];
            frac[0] = 1;
            for(int i = 1; i <= n; i++) frac[i] = frac[i - 1] * i;
            if(frac[n] < k) return "";
            LinkedList<Integer> nums = new LinkedList<Integer>();
            StringBuilder sb = new StringBuilder(n);
            for(int i = 0; i < n; i++) nums.addLast(i + 1);
            for(int i = n; i >= 1 && k > 0; i--){
                if(k == 1){
                    for(int p = 0; p < nums.size(); p++){
                        sb.append(nums.get(p));
                    }
                    break;
                }
                else if(k == frac[i]){
                    for(int p = nums.size() - 1; p >= 0; p--){
                        sb.append(nums.get(p));
                    }
                    break;
                }
                else if(k <= frac[i - 1]){
                    sb.append(nums.get(0));
                    nums.remove(0);
                }
                else{
                    int p = k / frac[i - 1];
                    if(k % frac[i - 1] > 0) p++;
                    k -= frac[i - 1] * (p - 1);
                    sb.append(nums.get(p - 1));
                    nums.remove(p - 1);
                }
            }
            return sb.toString();
        }
    }

Log in to reply
 

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