每日算法：Permutation Sequence

Permutation Sequence

 public static String getPermutation(int n, int k) {
        if (n == 1) {
            return "1";
        }
        //新建一个长度为n的数组每个数组元素就表第i个使用没有。
        boolean[] visited = new boolean[n+1];
        int[] dp = new int[n+1];
        //dp数组存放阶乘。
        dp[0] = 1;
        for (int i = 1; i < n+1; i++) {
            dp[i] = dp[i - 1] * i;
        }
        return perm(n, k, visited, dp);
    }

    public static String perm(int n, int k, boolean[] visited, int[] dp) {
        if(n == 0){
            return "";
        }
        int pos = 1;
        int cut = dp[n - 1];
        while (k > cut) {
            k -= cut;
            pos++;
        }
        String s = Integer.toString(getVisited(visited, pos));
        return s += perm(n - 1, k, visited, dp);
    }

    public static int getVisited(boolean[] visited, int index) {
        int o = 0;
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                o++;
            }
            if (o == index) {
                visited[i] = true;
                return i + 1;
            }
        }
        return 0;
    }