Algorithm

[LeetCode 60] Permutation Sequence [Java]

顿搜

2018-02-03

0 评论

892 阅读

正在检测是否收录...

02/03

1. Description

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 (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

2. Example

Given n = 3,k = 4
return "231"

3. Code

import java.util.ArrayList;
import java.util.List;

public class LeetCode0060 {
    public String getPermutation(int n, int k) {
        if (n < 0 || k < 0) {
            return null;
        }
        List numList = new ArrayList();
        int fractorial = 1;
        for (int i = 1; i <= n; i++) {
            numList.add(i);
            fractorial *= i;
        }
        k--;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            fractorial /= n - i;
            int index = k / fractorial;
            sb.append(numList.get(index));
            numList.remove(index);
            k %= fractorial;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LeetCode0060 leetcode = new LeetCode0060();
        System.out.println(leetcode.getPermutation(3, 4));
    }
}

Math

朗读