摘要:找规律复杂度时间空间思路由于我们只要得到第个全排列,而不是所有全排列,我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质,我们可以总结出一个规律假设全排列有个数组成,则第个全排列的第一位是。然后将得到,这个就是下一轮的。
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.
时间 O(N) 空间 O(1)
思路由于我们只要得到第K个全排列,而不是所有全排列,我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质,我们可以总结出一个规律:假设全排列有n个数组成,则第k个全排列的第一位是k/(n-1)!。为了更形象一点,举例如下:
123 132 213 231 312 321
在这种情况下,第一个数字每2!=2个情况就改变一次,假设求第6个排列,我们先将其减1,方便整除运算,然后5/2=2。对于第一位,我们有三种可选数字1、2、3,所以5/2=2意味着我们选择第3个数字,也就是3(如果商是s,则选第s+1个数字)。然后将5%2得到1,这个1就是下一轮的k。
注意这里有一个技巧,就是用一个列表将1到n存起来,每选用一个数就是移出那个数,就能保证不选重复数字的同时,其顺序也是一样的。
代码public class Solution { public String getPermutation(int n, int k) { int mod = 1; Listcandidates = new ArrayList (); // 先得到n!和候选数字列表 for(int i = 1; i <= n; i++){ mod = mod * i; candidates.add(i); } // 将k先减1方便整除 k--; StringBuilder sb = new StringBuilder(); for(int i = 0; i < n ; i++){ mod = mod / (n - i); // 得到当前应选数字的序数 int first = k / mod; // 得到用于计算下一位的k k = k % mod; sb.append(candidates.get(first)); // 在列表中移出该数字 candidates.remove(first); } return sb.toString(); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64559.html
摘要:题目要求假设按照题中给的排列组合的顺序,假设有个数字,返回第个排列组合的结果。最后在个位上,选择中的第一个。这时知道以第位为开头的结果值有此时第个结果集在该位上的选择为。依次往后类推,直至到最后一位。 题目要求 The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling...
摘要:我们所找到的这个元素就是排序需要改变的第一个元素。然后我们选取一个刚好大于此元素的数,与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。 题目详情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...
摘要:因为增加高位会带来更大的增益。所以对于一个长为的序列,我们增加第位的前提是,前位已经达到了最大排列方法。因为是找下一个数,所以我们要找一个比小却尽可能大的数,所以找到。把换到的位置后,后三位仍然是个降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...
摘要:题目要求也就是得出所有可能的排列组合结果解题思路和代码这题显然采用递归的思路。在这里,我采用实现队列,从队列头获得上一组的结果,和当前元素结合之后,将结果插入到队尾。 题目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...
阅读 2249·2021-11-15 11:37
阅读 2905·2021-09-01 10:41
阅读 730·2019-12-27 11:58
阅读 717·2019-08-30 15:54
阅读 689·2019-08-30 13:52
阅读 2895·2019-08-29 12:22
阅读 1042·2019-08-28 18:27
阅读 1418·2019-08-26 18:42