首页 > 代码库 > Permutation Sequence

Permutation Sequence

2024-07-19 11:16:48   219人阅读

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.

思路：使用标准库函数next_permutation循环k-1次求解将会超时。对于最高位n，其取值每加1，对应增加(n-1)!个排列实例。于是，对于给定的k，最高位的取值应为：(k-1) / (n-1)!。因此，可以考虑从高往低逐位确定每一位的取值。

 1 class Solution { 2 public: 3     string getPermutation( int n, int k ) { 4         int factorial = n; 5         string permutation, selection( n, ‘1‘ ); 6         for( int i = 1; i < n; ++i ) { 7             factorial *= i; 8             selection[i] += i; 9         }10         for( int i = 0; i < n && k > 0; ++i ) {11             factorial /= (n-i);12             int select = (k-1) / factorial;13             k %= factorial;14             permutation.push_back( selection[select] );15             selection.erase( select, 1 );16         }17         permutation.insert( permutation.end(), selection.rbegin(), selection.rend() );18         return permutation;19     }20 };

 

Permutation Sequence


联系
我们