Java Recursive Without Factorials-Array


  • 0
    S
    • I saw some Recursive solution use array to save factorials, which don't save space. And here is my code :) hope it helps.

    • Clear comment see here

    public class Solution {
        
        List<Integer> list = new ArrayList<Integer>();
        StringBuilder result = new StringBuilder();
        
        public String getPermutation(int n, int k) {
            
            for(int i = 0; i < n; i++) {
                list.add(i+1);
            }
            
            int total = 1;
            for(int i = 2; i <= n-1; i++) {
                total *= i;
            }
            
            return get(n-1, total, k);
            
        }
        
        private String get(int n, int interval, int k){
            
            if(list.size() == 1) {
                result.append(list.get(0));
                return result.toString();
            }
            int index = ((k-1) / interval) % list.size();
            result.append(list.get(index));
            list.remove(index);
            
            return get(n-1, interval/n, k);
            
        }
    }
    

Log in to reply
 

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