首页 > 其他 > 详细

LeetCode - Permutation Sequence

时间:2015-12-27 17:35:15      阅读:217      评论: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.

思路:

除法和求余运算,对每一组数往下递推

package permutation;

import java.util.ArrayList;
import java.util.List;

public class PermutationSequence {

    public String getPermutation(int n, int k) {
        List<Integer> l = new ArrayList<Integer>();
        for (int i = 1; i <= n; ++i) 
            l.add(i);
        --k;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; --i) {
            int fib = fib(i - 1);
            int index = k / fib;
            k = k % fib;
            sb.append((char)(‘0‘ + l.get(index)));
            l.remove(index);
        }
        return sb.toString();
    }
    
    private int fib(int n) {
        int res = 1;
        for (int i = 1; i <= n; ++i)
            res *= i;
        return res;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        PermutationSequence p = new PermutationSequence();
        System.out.println(p.getPermutation(4, 5));
    }

}

 

LeetCode - Permutation Sequence

原文:http://www.cnblogs.com/shuaiwhu/p/5080251.html

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