首页 > 其他 > 详细

60. Permutation Sequence

时间:2016-10-09 07:24:38      阅读:262      评论:0      收藏:0      [点我收藏+]

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

 

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

参考解析:http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html

思路:先算n!。.然后k/(n-1)!+1则为现在的第一个数字。更新k%=(n-1)!, n=n-1.

public class Solution {

    public String getPermutation(int n, int k) {
        if(n<=0)
        {
            return "";
        }
        List<Integer> list=new ArrayList<Integer>();
        int fac=1;
        
        for(int i=1;i<=n;i++)
        {
            list.add(i);
            fac*=i;
        }
        
        k--; //zero based
        
        StringBuilder sb=new StringBuilder();
        
        while(n>0)
        {
            fac/=n;
            sb.append(list.remove(k/fac));  //di ji zu
            
            k%=fac; //di ji ge 
            
            n--;
        }
        return sb.toString();
    }
}

 

 

 

 

60. Permutation Sequence

原文:http://www.cnblogs.com/Machelsky/p/5940776.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!