首页 > 代码库 > Permutation Sequence

Permutation Sequence

2024-11-10 14:48:39   203人阅读

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次就可以了，next permutation时间复杂度有点高，还需要优化一下

 1 public class Solution { 2      3     public String getPermutation(int n, int k) { 4         int num[] = new int[n]; 5         for(int i = 1; i <= num.length; i++){ 6             num[i - 1] = i; 7         }//初始化数组 8         for(int i = 1; i < k; i++){ 9             nextPermutation(num);10         }//for11         String result = "";12         for(int i = 0; i < num.length; i++){13             result += String.valueOf(num[i]);14         }15         16         return result;17     }18     19     /**20      * 获取下一个排列21      * @param num22      */23     private void nextPermutation(int[] num) {24         if(num.length == 0 || num.length == 1)25             return;26         boolean found = false;27         int index = 0;28         int comparaValue = http://www.mamicode.com/0;29         for(int i = num.length - 1; i > 0; i--){        //找出出现降序的位置30             if(num[i] > num[i - 1]){                    //这里不能交换31                 index = i;32                 comparaValue = http://www.mamicode.com/i - 1;33                 break;34             }//if35         }//for36 37             int min = index;38             for(int i = min; i < num.length; i++){39                 if(num[i] > num[comparaValue] && num[i] < num[min]){40                     min = i;41                 }//if                42             }//for43             int temp = num[min];44             num[min] = num[comparaValue];45             num[comparaValue] = temp;46             47             //对index后面的进行升序排列48             for(int i = index; i < num.length; i++){49                 min = i;50                 for(int j = i + 1; j < num.length; j++){51                     if(num[min] > num[j])52                         min = j;53                 }//for54                 if(min != i){55                     temp = num[min];56                     num[min] = num[i];57                     num[i] = temp;58                 }59             }60         61     }62 }

 

Permutation Sequence


联系
我们