Share my easy understand solution with comments - Java


  • 8
    L
     public int nFatorial(int n ) {
        	if(n == 0)
        		return 1;
        	return n * nFatorial(n - 1);
     }
    
    public String getPermutation(int n, int k) {
        	if(n == 0)
        		return "";
        	
        	String res = "";
    
        	// numbers to be added to result string
            List<Integer> num = new ArrayList<Integer>();
            
            // initialization, 0 just for padding
            for(int i = 0; i <= n; i++)
            	num.add(i);
            
            int factorial;
            int index;
            
            for(int i = n; i > 0; i--) {
            	factorial = nFatorial(i - 1);
    
            	// calculate current number index
            	index = (int) Math.ceil(k / (double) factorial);
            	
            	res += num.get(index);
            	
            	// after adding, delete it from rest set
            	num.remove(index);
            	
            	// update k for the next loop
            	k = k % factorial;
            	if(k == 0)
            		k = factorial;
            }
            return res;
    }

  • 0
    W

    Really smart for adding 0 as padding


  • 0
    S

    good, but you didn't need to count fatorial every time.
    just like this:

    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.