15ms concise JAVA solution, O(n) with comments


  • 0
    public class Solution {
        /*
        Idea: construct the target sequence from the most significant position
        
        Method: 1: construct a table to store the total permutation number for each position
                e.g. if n = 5 then table[] = {1, 2, 6, 24, 120} which are 1!, 2!, 3!, 4! and 5!
                   construct a boolean table to store which number are used among [1, n], here [1, 5] are {f,f,f,f,f}
                2: Suppose the target label is k, where k <= 120 according to the quesiton. 
                   To determine the first number:
                   a) if k == 120, return 54321
                   b) if k < 24, it means the permutation does not involve the arrangement of the highest postion, 
                        The first number is the first unused number, in this case, 1, meanwhich set used[1] = true;
                   c) if k < 120 && k > 24 ==> k/24 = a; k%24 = b;
                        if b == 0, it means there are b total permutation of 24
                        e.g. if a == 1, return 15432
                             if a == 2, return 25431
                             the current positions' number is the 'ath' unused number. 
                             Then, append all unused number in descending order will give the answer
                        if b != 0, it means there are b total permutaion of 24 and partial permutation of 24
                             find the '(a + 1)th' unused number
                             assign k = b to keep finding the rest
        performance :   Time O(n)
                        15ms pretty good 
                        
        */
        public String getPermutation(int n, int k) {
            int[] table = new int[n + 1];
            table[1] = 1;
            for (int i = 2; i <= n; i++) {
                table[i] = table[i - 1] * i;
            }
            StringBuilder sb = new StringBuilder();
            boolean[] used = new boolean[n + 1];
            int index = n;
            while (k > 0 && k < table[index]) {
                while (table[index] > k) {
                    index --;
                    if (table[index] > k) {
                        addOne(used, sb, 1);
                    }
                }
                int div = k / table[index];
                k %= table[index];
                div += k == 0 ? 0 : 1;
                addOne(used, sb, div);
            }
            for (int i = n; i >= 1; i --) {
                if (!used[i]) {
                    sb.append(i);
                }
            }
            return sb.toString();
        }
        
        public void addOne(boolean[] used, StringBuilder sb, int pos) {
            for (int i = 1; i < used.length; i ++) {
                if (!used[i] && --pos == 0) {
                    sb.append(i);
                    used[i] = true;
                }
            }
        }
    }
    

Log in to reply
 

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