首页 > 代码库 > Leetcode-Permuation Sequence

Leetcode-Permuation Sequence

2024-08-02 12:27:55   221人阅读

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 1:

We use recursive method to get the sequence one by one. However, this method is slow.

 1 public class Solution { 2     public String getPermutation(int n, int k) { 3         int[] seq = new int[n+1]; 4         int level = 1; 5         boolean[] used = new boolean[n+1]; 6         Arrays.fill(used,false); 7         Arrays.fill(seq,0); 8         used[0] = true; 9         int count = 0;10         String res = "";11         while (true){12             if (level==n){13                 count++;14                 if (count==k){15                     for (int i=1;i<=n;i++)16                         if (!used[i]){17                             seq[level] = i;18                             break;19                         }20                     for (int i=1;i<=n;i++)21                         res += Integer.toString(seq[i]);22                     break;23                 } else {24                     level--;25                     continue;26                 }       27             }28 29             int val = seq[level];30             //NOTE: we need the first condition, because used array does not have n+1.31             while (val<n+1 && used[val])32                 val++;33             if (val==n+1){34                 if (seq[level]!=0) used[seq[level]] = false;35                 seq[level]=0;36                 level--;37                 continue;38             } else {39                 if (seq[level]!=0) used[seq[level]] = false;40                 seq[level] = val;41                 used[val]=true;42                 level++;43             }44         }45 46         return res;47         48     }49 }

Solution 2:

We actually can calculate the sequence. For sequences with n numbers, it is composed by n segments of sequences with n-1 numbers. The number of (n-1) sequences in each segment is (n-1)!. So if we are looking for kth n sequence, it is in (k/(n-1)!)th or (k/(n-1)!+1)th segment (boundary case considerred) which is means the number in the first place should be the (k/(n-1)!)th available number between 1 and n. The number of sequences we should count in this segment to find the target is (k%(n-1)!)th sequence in this segement. With this recurrence formula, we can directly calculate the string one place by one place.

NOTE: We need to consider the boundary cases where k%(n-1)!==0, in this case, it is the (n-1)!th sequence in the k/(n-1)! segment. 

 1 public class Solution { 2     public String getPermutation(int n, int k) { 3         int[] seq = new int[n+1];         4         boolean[] used = new boolean[n+1]; 5         Arrays.fill(used,false); 6         Arrays.fill(seq,0);         7         String res = ""; 8         int[] val = new int[n+1]; 9         val[0] = 0;10         val[1] = 1;11         for (int i=2;i<=n;i++)12             val[i] = val[i-1]*i;13         14         int left = k;15         int num = n;16         for (int i=1;i<n;i++){17             int interval = val[num-1];18             int step = left/interval;19             int nextLeft = left%interval;20             if (nextLeft==0)21                 nextLeft = interval;22             else step++;23             int index=0;24             for (int j=1;j<=n;j++)25                 if (!used[j]){26                     index++;27                     if (index==step){28                         seq[i]=j;29                         used[j] = true;30                         break;31                     }32                 }33              left = nextLeft;34              num--;35          }36          for (int i=1;i<=n;i++)37              if (!used[i]){38                  seq[n]=i;39                  break;40              }41 42          for (int i=1;i<=n;i++)43              res += Integer.toString(seq[i]);44          return res;45         46     }47 }

 

Leetcode-Permuation Sequence


联系
我们