Another solution in Java with explanation. no loop, no swap. Easy Understanding. 200ms


  • 1
    Z
    public String getPermutation(int n, int k) {
        List<Integer> participate = new ArrayList<>(n);
        if (n <= 1) {
            return "1";
        }
        for (int i = 1; i <= n; i++) {
            participate.add(i);//build an initial list
        }
        return recur(n, k - 1, participate, new StringBuilder(n));//k-1 for get element from list
    }
    
    private String recur(int n, int k, List<Integer> participate, StringBuilder sb) {
        if (n == 2) {
            sb.append(participate.get(k));
            participate.remove(k);
            sb.append(participate.get(participate.size() - 1));
            return sb.toString();
        }
        int x = fac(n); // x: sequence length Example: n = 5, there are 5 sequences start with 1 to 5, each sequence has 24 items
        int i = k / x; // i: which sequence the search k it belong. Example: n=4 k=8, i=(8-1)/6=1. so the start number should be 2
        sb.append(participate.get(i));
        participate.remove(i);
        return recur(n - 1, k % x, participate, sb);
    }
    
    private int fac(int n) {
        int sum = 1;
        for (int i = 1; i < n; i++) {
            sum *= i;
        }
        return sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.