首页 > 其他 > 详细

LeetCode | Permutation Sequence

时间:2014-03-23 11:46:59      阅读:435      评论:0      收藏:0      [点我收藏+]

题目

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.

分析

如果挨个搜的话,恐怕会超时。

那就用算的方式,以n=3, k=3为例:

由于我们是从0开始计数,k -= 1;

首先,初始化一个链表list,list中的元素依次为:1, 2, 3;

获取第一位数字:k / 2! = 1,第一个数字就是list.get(1) = 2,同时,从链表中删除已经使用的元素list.remove(1),list剩余数字:1, 3,并且k = k % 2! = 0;

获取第二个数字:k / 1! = 0,第二个数字就是list.get(0) = 1,同时,从链表中删除已经使用的元素list.remove(0),list剩余数字:3,由于已达到最后一位,不需要操作k了。

获取第三个(最后)数字:list剩余的元素,即list.get(0) = 3。

最终三个数字为213。

按照这个思路代码如下。

代码

import java.util.LinkedList;
import java.util.List;

public class PermutationSequence {
	public String getPermutation(int n, int k) {
		// get permutation num
		int[] permutation = new int[n];
		permutation[0] = 1;
		for (int i = 1; i < n; ++i) {
			permutation[i] = permutation[i - 1] * (i + 1);
		}

		// num list that can be used
		List<Integer> list = new LinkedList<Integer>();
		for (int i = 1; i <= n; ++i) {
			list.add(i);
		}

		// process
		StringBuilder sb = new StringBuilder();
		int pos = n - 1;
		k -= 1;
		while (pos > 0) {
			int index = k / permutation[pos - 1];
			sb.append(list.get(index));
			list.remove(index);
			k = k % permutation[pos];
			--pos;
		}
		sb.append(list.get(0));
		return sb.toString();
	}
}

LeetCode | Permutation Sequence,布布扣,bubuko.com

LeetCode | Permutation Sequence

原文:http://blog.csdn.net/perfect8886/article/details/21858643

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!