Java Recursive and Iterative


  • 3

    Iterative:

        public String getPermutation(int n, int k) {
            
            // e.g n = 5
            // [1][1][2][6][24]
            int[] factorial = new int[n];
            factorial[0] = 1;
            
            for(int i = 1; i < n; i++) {
                factorial[i] = factorial[i-1] * i;
            }
            
            ArrayList<Integer> numbers = new ArrayList<>();
            for(int i = 1; i <= n; i++) {
                numbers.add(i);
            }
            
            String res = "";
            for(int i = n-1; i >= 0; i--) {
                
                int num = (k-1)/factorial[i];
                res += numbers.get(num);
                k -= num * factorial[i];
                numbers.remove(num);
            }
            
            return res;
        }
    

    Recursive:

        public String getPermutation(int n, int k) {
            
            // recursive
            // how do you make the problem smaller?
            List<Integer> list = new ArrayList<>();
            // 1,1,2,6
            int[] factorials = new int[n];
            factorials[0] = 1;
            for(int i = 1; i < n; i++) {
                factorials[i] = factorials[i-1] * i;
            }
            
            for(int i = 1; i <= n; i++) {
                list.add(i);
            }
            
            return helper(list, k, factorials);
        }
        
        private String helper(List<Integer> list, int k, int[] factorials) {
            
            if(list.size() == 0) {
                return "";
            }
    
            int num = (k-1)/factorials[list.size()-1];
            String str = "" + list.get(num);
            k -= num * factorials[list.size()-1];
            list.remove(num);
    
            return str+helper(list, k, factorials);
        }
    

  • 0
    I

    太强了!!!!!!茅塞顿开!!!!!无敌!!!!


  • 0
    S

    hey, I think if you use recursive solution, you don't need to use factorials array.

    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.