Permutation Sequence, Leetcode 解题笔记

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

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

第一思路肯定是DFS枚举,跟之前的Permutation I && II 类似。只是这次不用枚举所有的结果,而是只到第k个就行了。但是这种方法时间复杂度太高了,过不了OJ。

第二思路是数学方法,算出第k个时每个数字的位置。这种方法只适用于这一道题,没有什么可移植性,了解一下就好。

DFS枚举:

public class Solution {

    int count = 0;
    String ret = "";
    char [] dic = {'1','2','3','4','5','6','7','8','9'};
    public String getPermutation(int n, int k) {
        StringBuilder s = new StringBuilder();
        int[] visited = new int[n];
        dfs(n, k, s, 0, visited);
        return ret;
    }

    public void dfs(int n, int k, StringBuilder s, int deep, int[] visited){
        if(deep == n){
            count++;
            if(count == k){
                ret = s.toString();
                return;
            }
        }
        for(int i = 0; i < n; i++){
            if(visited[i] == 0){
                s.append(dic[i]);
                visited[i] = 1;
                dfs(n, k, s, deep+1, visited);
                s.deleteCharAt(s.length()-1);
                visited[i] = 0;
            }

        }
    }
}

数学:

public class Solution {
	public String getPermutation(int n, int k) {
 
		// initialize all numbers
		ArrayList<Integer> numberList = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			numberList.add(i);
		}
 
		// change k to be index
		k--;
 
		// set factorial of n
		int mod = 1;
		for (int i = 1; i <= n; i++) {
			mod = mod * i;
		}
 
		String result = "";
 
		// find sequence
		for (int i = 0; i < n; i++) {
			mod = mod / (n - i);
			// find the right number(curIndex) of
			int curIndex = k / mod;
			// update k
			k = k % mod;
 
			// get number according to curIndex
			result += numberList.get(curIndex);
			// remove from list
			numberList.remove(curIndex);
		}
 
		return result.toString();
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s