leetcode 60 Permutation Sequence
z
 2018-05-20 19:58:08  

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

分析，对于n=3，k=5；

对于n=3的排列：

  • 1 + {2,3}的排列
  • 2 + {1,3}的排列
  • 3 + {1,2}的排列

确定最高位数值 = k-1 / (n-1)!

确定最高位后，下一位的确定和最高位一样，即可以依次迭代下去。

要注意一点，在确定完一位之后，后面的数值排列需要按照从小到大的顺序排列。

可以使用一个StringBuilder，开始时，StringBuilder中的数值为：1-n;

每确定一位，将这一位append到StringBuilder末尾，同时删除原位置的数值。

考虑到当n很大时，例如n=8时，对于k=3，前面的5位顺序未发生变化。同样的，我们每次将StringBuilder中的第0位的数值append到最后，并删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder ans = new StringBuilder();
        int[] fac = new int[n];
        // 构造初始的答案：1234...n
        for(int i=1; i<=n; i++){
            ans.append((char) ('0' + i));
        }
        // 构造阶乘数组[1,1,2,6,...,(n-1)!]
        fac[0] = 1;
        for(int i=1; i<n; i++){
            fac[i] = fac[i-1]*i;
        }
   		// k用来映射到stringbuilder的下标，因此需要减一，
        // 如果不减一的话，可以考虑n=3，k=6的情况，index将为3，超过边界了。
        k = k-1;
        for(int i=n-1; i>=0; i--){
            // 找到需要append到末尾的index
            int index = k/fac[i];
            ans.append(ans.charAt(index));
            ans.deleteCharAt(index);
            k = k % fac[i];
        }
        return ans.toString();
        
    }
}

1 {2, 3, 4} 6
2 {1, 3, 4} 6
3 {1, 2, 4} 6
4 {1, 2, ,3} 6