首页 > 代码库 > [LeetCode] Permutation Sequence

[LeetCode] Permutation Sequence

2024-07-09 10:44:34   223人阅读

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 的关系，所以只能使用时间复杂度O(n^n)的排序树。。每个位置都有n中可能，记录下已经使用的数字，然后从未使用的数据中选择，然后递归调用，其实使用的还是回溯法的框架，有所更改。

上Code，但是大数时会超时。。

 

 1 class Solution { 2         vector<bool> m_avaliable; 3         int m_k; 4         int m_cnt; 5         vector<int> m_array; 6     public: 7         string m_str; 8  9         void dfs_permutation(int size, int dep)10         {11             if(dep == size)12             {13                 m_cnt ++;14                 if(m_cnt == m_k)15                 {16                     for(int i = 0; i < size; i++)17                     {18                         m_str += m_array[i] + ‘1‘;19                     }20                     return;21                 }22             }23 24             //dfs to the next level25             // every level has size choices, its time complexity is O(n^n)26             for(int i = 0; i < size; i++)27             {28                 if( m_avaliable[i] == true)29                 {30                     //cout <<"dep = " <<dep <<endl;31                     //cout <<"i   = " <<i <<endl;32                     m_array[dep] = i;33                     m_avaliable[i] = false;34                     dfs_permutation( size, dep+1);35                     m_avaliable[i] = true;36                 }37 38             }39 40 41 42         }43         string getPermutation(int n, int k)44         {45             //initinalize the member variable46             m_avaliable.resize(n, true);47             m_array.resize(n);48             m_k = k;49             m_cnt = 0;50             m_str.clear();51 52             //call dfs53             dfs_permutation(n, 0);54 55             // return 56             return m_str;57         }58 59 };

 


联系
我们