首页 > 代码库 > 【LeetCode】Permutation Sequence

【LeetCode】Permutation Sequence

2024-08-07 07:24:07   214人阅读

Permutation Sequence

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.

 

我的方法从高位到低位逐位确定数字。

以图例n=3进行说明：

构建数组v={1,2,3}

确定最高位：

ind=(k-1)/2

注：分母2是指每个最高位持续的排列数。由于除了最高位之外还有n-1=2位，一共可以出现2!种排列。

ind指的是所求的第k个排列会落在哪一个最高位的覆盖范围内。

k==1,2时，ind==0，最高位为v[ind]==1

k==3,4时，ind==1，最高位为v[ind]==2

k==5,6时，ind==2，最高位为v[ind]==3

其余数位如上思路逐位确定。注意k的取余更新。

class Solution {public:    string getPermutation(int n, int k) {        vector<int> v(n, 0);        for(int i = 0; i < n; i ++)            v[i] = i+1;        string result = "";        while(n-1)        {            int divisor = fac(n-1);            int ind = (k-1)/divisor;            //itoa            string digit;            char temp[32];            sprintf(temp, "%d", v[ind]);            digit = temp;                    result += digit;            for(int i = ind+1; i < v.size(); i ++)                v[i-1] = v[i];            v.pop_back();            k %= divisor;            if(k == 0)                k = divisor;            n --;        }        //itoa        string digit;        char temp[32];        sprintf(temp, "%d", v[0]);        digit = temp;                result += digit;        return result;    }    int fac(int n)    {        if(n == 0)            return 1;        int result = 1;        for(int i = 1; i <= n; i ++)            result *= i;        return result;    }};

 

【LeetCode】Permutation Sequence


联系
我们