60. Permutation Sequence

Permutation Sequence - LeetCodeLeetCode

permutation 這類的題目主要有三種

1. 全排列 permutation

https://leetcode.com/problems/permutations/

https://leetcode.com/problems/permutations-ii/

2. kth permutation

https://leetcode.com/problems/permutation-sequence/

3. next permutation

https://leetcode.com/problems/next-permutation/

kth permutation

http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html

1. "123"

2. "132"

3. "213"

4. "231"

5. "312" => 5th

6. "321"

1 => 後兩位的排列數, 即 2! = 2*1 , 即f(n-1) 代表後面階層會經過的序列

123

132

2 =>

213

231

3 =>

312

321

nums = [1, 2, 3]; // 儲存了要排列的數字

所以要得到第一位是什麼數字,

k--; // 化為起始 0 開始的序列 // k = 4

k = k / f(n-1) // 這樣就會得到第一位的 index

k = 4/2 = 2, index 2 = nums[2] = 3

k = k % f(n-1); // 下輪要繼續跑的數字, 即 k 減掉 我們剛剛pass過的序列

O(n^2), nums.remove(), 需要O(n)

but Given n will be between 1 and 9 inclusive.

so time complexity is small

space complexity: O(n)

class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        int[] f = new int[n];
        List<Integer> nums = new ArrayList<>();
        f[0] = 1;
        
        
        for (int i = 1 ; i < n ; i++) {
            f[i] = i*f[i-1];
            nums.add(i);
        }
        nums.add(n);
        k--;
        
        for (int i = n; i > 0; i--) {
            int idx = k/f[i-1];  
            k = k % f[i-1];
            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}