当前位置:网站首页>Leetcode 60 kth permutation

Leetcode 60 kth permutation

2020-11-13 20:03:56 Want to exchange steamed stuffed bun for thesis

LeetCode60 The first k Permutation

Title Description

Give set [1,2,3,...,n], All of its elements have n! Species arrangement .

List all permutations in order of size , And mark one by one , When n = 3 when , All arranged as follows :

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, Back to page k Permutation .

Examples

 Input :n = 3, k = 3
 Output :"213"
 Input :n = 4, k = 9
 Output :"2314"
 Input :n = 3, k = 1
 Output :"123"

Algorithm analysis

  • Enumerate each location
  • Consider each bit from high to low ;
  • For everyone , Enumerate the unused numbers from small to large , Determine what the current bit is

Time complexity

Java Code

class Solution {
    public String getPermutation(int n, int k) {
        boolean[] st = new boolean[10];
        int[] f = new int[10]; // Existential factorial 
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            f[i] = f[i - 1] * i;
        }

        String ans = "";
        for(int i = 0; i < n; i ++){
            for(int j = 1; i <= n; j++){
                if(!st[j]){
                    if(k <= f[n-i-1]){
                        ans = ans + "" + j;
                        st[j] = true;
                        break;
                    }
                    k -= f[n-i-1];
                }
            }
        }

        return ans;
    }
}

版权声明
本文为[Want to exchange steamed stuffed bun for thesis]所创,转载请带上原文链接,感谢