`
huntfor
  • 浏览: 201541 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Permutation Sequence

 
阅读更多

算法还是一样的算法,但是新博文的代码更简洁,可读性更好,新博文地址:[leetcode]Permutation Sequence

Permutation Sequence

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.

这道题思路很简单,但是实现起来用的时间比较长,可能是思路不太清晰,或者几天没做题手生了吧。题中要求是给出数字n,则由1~n可组成n!的组合,将组合数从小到大排序,求出第k个组合数。

 

最直观的思路无非是求出n!个组合情况,将其排序,然后求出第k个。事实上,想一下就知道这是不可能做到的,当n不需要很大,比如n = 100时,n!已经是很大的数了,可能已经溢出了,想其时间复杂度O(n!)更是早就超时了,因此不能这样做。

 

不得不换种思路,不需要求出所有的组合数。甚至直接求第K个组合数。到底该怎么做呢?

有几点条件是可以使用的。组合数都是从小到大排序的。去掉高位之后,低位数字同样从小到大排序,因此可以考虑用递归。

来看题中给的例子:

123 -- 第1个loop

132 -- 第1个loop

213 -- 第2个loop

231 -- 第2个loop

312 -- 第3个loop

321 -- 第3个loop

我们可以根据k确定最高位的数字:

因为去掉最高位还剩下2位,这两位数字可以组成(n - 1)!种组合(记作factorial),再求出其在哪个loop中

如果k <=  factorial,肯定在第1个loop,如果k > factorial,比如k = 5,那么应该在 5 / 2 = 2第2个loop,但是当k = 6时,在6/ 2个loop,但是k = 5或k = 6是在同一个loop中,区别就是一个有余数,一个是整除,简单处理之。

好了,当k = 5,求出第一位应该是3,然后标记3已经用过了,跨过了两个loop,即跨过了loop * factorial——4种组合,只需要递归从1、2组成的组合中找到第1个子组合即可。

 

大致算法思想就是这样。出口为确定了n位数字或者k = 1(这个自己想哈)

代码实现为:

 

public String getPermutation(int n, int k) {
		boolean[] hash = new boolean[n];
		if (n < 1) {
			return null;
		}
		int factorial = 1;
		for (int i = 0; i < n; hash[i] = true, factorial *= (1 + i), i++);
		if (factorial < k) {
			return null;
		}
		return dfs(hash, k, 0);
	}

	/**
	 * @param hash
	 * @param k
	 *            means find the k_th number in factorial
	 * @param n
	 *            means has confirmed n prefix numbers
	 * @return
	 */
	private String dfs(boolean[] hash, int k, int n) {
		StringBuilder sb = new StringBuilder();
		if(n == hash.length){
			return "";
		}
		if (k == 1) {
			int i = 0;
			while (i < hash.length) {
				if (hash[i]) {
					sb.append(i + 1);
				}
				i++;
			}
			return sb.toString();
		}
		int factorial = 1;
		for (int i = 1; i <= hash.length - n - 1; factorial *= i, i++);
		int loop = 0;
		if (k > factorial) {
			loop = k / factorial + 1;
			if(k % factorial == 0) loop--;
		} else {
			loop = 1;
		}
		for (int count = 0, i = 0; i < hash.length; i++) {
			if (hash[i]) {
				count++;
				if (count == loop) {
					sb.append(i + 1);
					hash[i] = false;
					break;
				}
			}
		}
		if(k > factorial) return sb.append(dfs(hash, k - (loop - 1)* factorial, n + 1 )).toString();
		else return sb.append(dfs(hash, k, n + 1)).toString();
	}

 

 

 

分享到:
评论

相关推荐

    java-leetcode题解之Permutation Sequence.java

    java java_leetcode题解之Permutation Sequence.java

    js-leetcode题解之60-permutation-sequence.js

    js js_leetcode题解之60-permutation-sequence.js

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) !... Up to date (2016-12-18), there are `447` Algorithms / `13` ...31 | [Next Permutation](https://leetcode.com/problems/next-permutation/)| ...

    lrucacheleetcode-LeetCode:这个库用于总结leetcode中遇到的习题,期望按照数据结构和常用方法分成2类,进行总结,

    leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array II 3 ...

    leetcode代码200题c++

    1. **Permutation Sequence**:这个问题涉及到排列组合和字符串操作。它要求生成一个给定整数n的所有可能排列的序列。这通常需要对数字进行位操作或使用回溯法。 2. **First Missing Positive**:这是一个关于数组...

    c++-c++编程基础之leetcode题解第60题排列序列.zip

    LeetCode的第60题,也称为"排列序列"(Permutation Sequence),要求我们给定一个整数n,生成所有可能的n个数字的排列,并按照字典序排序。例如,当n=3时,排列序列应该是"123", "132", "213", "231", "312", "321...

    Coding Interview In Java

    236 Permutation Sequence 573 237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number ...

    leetcode-cpp刷题

    - **2.1.13 Permutation Sequence** - 给定数字集合,返回第n个排列。 - 实现思路:利用数学方法计算出每一位上的数字。 - **2.1.14 Valid Sudoku** - 判断给定的数独是否有效。 - 实现思路:分别检查行、列和...

    leetcode_basic_60

    这个“leetcode_basic_60”主题可能聚焦于LeetCode上的第60题,即“Permutation Sequence”(排列序列)。这个问题涉及到组合数学、递归和字符串处理,是Python编程者常见的练习题目。 【描述】"leetcode_basic_60...

    javalruleetcode-SDE-Problems:标准SDE问题列表

    leetcode SDE-问题 标准 SDE 问题列表 第一天:(数组) 日 问题陈述 解决方案 困难 使用的数据结构 使用的算法 时间复杂度 空间复杂度 补充阅读 在 N 个整数的数组中查找重复项 中等的 大批 不适用 上) O(1) 在不...

Global site tag (gtag.js) - Google Analytics