60. Permutation Sequence

二刷

Time O(N^N)

Space O(N)

Runtime: 2 ms, faster than 85.36% of Java online submissions for Permutation Sequence.

Memory Usage: 41.3 MB, less than 62.80% of Java online submissions for Permutation Sequence.

class Solution {

    public String getPermutation(int n, int k) {

        StringBuilder sb = new StringBuilder();

        List<Integer> nums = new ArrayList<>();

        int[] factorial = new int[n + 1];

        factorial[0] = 1;

        // fact[1] = 1 * fact[0] = 1

        // fact[2] = 2 * fact[1] = 2

        for (int i = 1; i <= n; i++) {

            nums.add(i);

            factorial[i] = i * factorial[i - 1];

        }

        // k = 3, n = 3, factorial[n - 1] = fact[2] = 2

        // 1 -> 0 "123"

        // 2 -> 1 "132"

        // 3 -> 2 "213"

        // 4 -> 3 "231"

        // 5 -> 4 "312"

        // 6 -> 5 "321"

        while (k > 0 && n > 0) {

            n--;

            int index = (k - 1) / factorial[n]; // index = 1;

            Integer num = nums.get(index);

            sb.append(num);

            k -= factorial[n] * index;

            nums.remove(num);

        }

        return sb.toString();

    }

}

一刷

http://blog.csdn.net/qq508618087/article/details/51635302
The logic is as follows: for n numbers the permutations can be divided to (n-1)! groups, for n-1 numbers can be divided to (n-2)! groups, and so on. Thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining index for the remaining n-1 numbers.
We keep doing this until n reaches 0, then we get n numbers permutations that is kth.

29.54%
注意这里k是从1开始的，所以initialize k = k - 1;
public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) return null;
        int factorial = 1;
        List<Integer> bits = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            bits.add(i);
            factorial *= i;
        }
        if (k > factorial) return null;
        k = k - 1;
        StringBuilder sb = new StringBuilder();
        for (int position = 0; position < n; position++) {
            //(n - 1)!
            factorial /= (n - position);
            int index = k / factorial;
            k = k % factorial;
            sb.append(bits.get(index));
            bits.remove(index);
        }
        return sb.toString();
        
    }

}