算法还是一样的算法,但是新博文的代码更简洁,可读性更好,新博文地址:[leetcode]Permutation Sequence
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(); }
相关推荐
Source file for LeetCode Permutations Problem
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
100个leetCode详细解答
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
LeetCode面试笔试题
LeetCode 刷题
leetcode全套解答python版本。包括更新到10月份的的leetcode