Leetcode–Permutation Sequence

The Problem:

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.

Notes:

  1. The key is to use an array or list to record the numbers to be added, then can access that number just according to the index calculated from k. Also I used linkedlist to store the numbers which makes it easier to remove each number after chosen.
  2. input k should be decreased first before treating as index

Java Solution

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new LinkedList<Integer>();
        int multiplys = 1;
        for(int i= 0; i<n; i++){
            multiplys= multiplys*(i+1);
            numbers.add(i+1);
        }
        
        k--; //---!! k is not array index
        StringBuilder result  = new StringBuilder();
        for(int i =0; i < n; i++){
            multiplys = multiplys/(n-i);
            int index = k/multiplys;
            result.append(numbers.get(index));
            numbers.remove(index);
            k = k%multiplys;
        }
        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