首页 > 其他 > 详细

[LeetCode] Permutation Sequence

时间:2014-03-20 18:23:13      阅读:246      评论: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.

Solution:

bubuko.com,布布扣
class Solution {
public:
    string getPermutation(int n, int k) {
    string ans = "";
    int *fact = new int[n + 1];
    int *data = new int[n + 1];
    fact[0] = 1;
    fact[1] = 1;
    for(int i = 1;i <= n;i++)
    {
        data[i] = i;
        fact[i] = fact[i - 1] * i;
    }

    int tmpK = k;
    for(int i = 1; i <= n;i++)
    {
        int ind = (tmpK - 1) / fact[n - i] + 1;
        tmpK = (tmpK - 1) % fact[n - i] + 1;
        int num_loc = 0;//current number‘s index in the remaining number list
        for(int j = 1;j <= n;j++)
        {
            if(data[j] != 0)
            {
                num_loc++;
                if(num_loc == ind)
                {
                    //this is the desire number for this location
                    ans += data[j] + 0;
                    data[j] = 0;
                    break;
                }
            }
        }
    }

    return ans;
    }
};
bubuko.com,布布扣

[LeetCode] Permutation Sequence,布布扣,bubuko.com

[LeetCode] Permutation Sequence

原文:http://www.cnblogs.com/changchengxiao/p/3614110.html

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