b****g 发帖数: 192 | 1 一串1~9的整数,比如11635,是由1、1、3、5、6这五个数字组成的。
把这五个数字做成的所有字符串按顺序排列出来:
11356 -- 排第1
11365 -- 排第2
11536 -- 排第3
11563 -- 排第4
11635 -- 排第5
11653
13156
...
现在要求写一个函数,输入11635,输出5,因为11635在上面的那些字符串里排第5。
怎么做?生成所有排列在找11635肯定不行,太慢了。
我只会用leetcode里的next permutation一个一个数出来,速度也太慢了。 |
z****e 发帖数: 54598 | 2 这个是一个排列组合题
给你一个数字
问,你用这些数字能组合出多少个比这个数字更小的数 |
b****g 发帖数: 192 | 3 怎么做呢?
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是一个排列组合题 : 给你一个数字 : 问,你用这些数字能组合出多少个比这个数字更小的数
|
p*****2 发帖数: 21240 | 4
Leetcode上有这道题吧?
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一串1~9的整数,比如11635,是由1、1、3、5、6这五个数字组成的。 : 把这五个数字做成的所有字符串按顺序排列出来: : 11356 -- 排第1 : 11365 -- 排第2 : 11536 -- 排第3 : 11563 -- 排第4 : 11635 -- 排第5 : 11653 : 13156 : ...
|
r**h 发帖数: 1288 | 5 这题首先就应该把数字转换成字符串吧?
leetcode上的那道题没有重复的元素,要简单一些呀
(不过那题要写对感觉也不简单啊)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : Leetcode上有这道题吧?
|
p*****2 发帖数: 21240 | 6
leetcode上的是要简单一些。
【在 r**h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题首先就应该把数字转换成字符串吧? : leetcode上的那道题没有重复的元素,要简单一些呀 : (不过那题要写对感觉也不简单啊)
|
b****g 发帖数: 192 | 7 你是说Permutation Sequence那道题吗?
那个题是已知k,求第k个permutation。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : leetcode上的是要简单一些。
|
p*****2 发帖数: 21240 | 8
意思差不多吧?
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是说Permutation Sequence那道题吗? : 那个题是已知k,求第k个permutation。
|
b****g 发帖数: 192 | 9 我问的题是:已知某个permutation,求它是第几个。和leetcode的刚好相反。
我只会用leetcode里next permutation那种方法做:
从第1个逐步使用next permutation那题的方法,依次生成下一个permutation,
直到达到了我的目标。
比如,函数输入是11635,
那么我就依次生成 11356 -> 11365 -> 11536 -> 11563 -> 11635,
找了5次,于是输出5.
刚好和leetcode的Permutation Sequence要求相反。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 意思差不多吧?
|
p*****2 发帖数: 21240 | 10
复杂度有点高吧?N!吧。
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我问的题是:已知某个permutation,求它是第几个。和leetcode的刚好相反。 : 我只会用leetcode里next permutation那种方法做: : 从第1个逐步使用next permutation那题的方法,依次生成下一个permutation, : 直到达到了我的目标。 : 比如,函数输入是11635, : 那么我就依次生成 11356 -> 11365 -> 11536 -> 11563 -> 11635, : 找了5次,于是输出5. : 刚好和leetcode的Permutation Sequence要求相反。
|
b****g 发帖数: 192 | 11 没错!
所以我才来请教大家啊!!!
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 复杂度有点高吧?N!吧。
|
p*****2 发帖数: 21240 | 12
11356可以转化为00123
然后
00123 -> 1
00132 -> 2
看00123的时候, 可以转化为00000
0 skip
0 skip
1 因为已经用了两个0了,1就是剩下元素里的第0个元素, skip
2 剩下元素的0, skip
3 剩下元素的0,skip
因此, 00123就是最小的元素就是1
00132, 可以转化为00010
0 skip
0 skip
1 skip
3, 是剩下元素的1, 在它前边是有1!个元素,
2 skip,
00132之前有1个元素,因为00132就是2
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没错! : 所以我才来请教大家啊!!!
|
b****g 发帖数: 192 | 13 我想明白了,和leetcode的Permutation Sequence思路一样
一半一半的找。
每次都找一个阶乘那么多。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 11356可以转化为00123 : 然后 : 00123 -> 1 : 00132 -> 2 : 看00123的时候, 可以转化为00000 : 0 skip : 0 skip : 1 因为已经用了两个0了,1就是剩下元素里的第0个元素, skip : 2 剩下元素的0, skip
|
c********p 发帖数: 1969 | 14 不是next permutation么?
【在 b****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是说Permutation Sequence那道题吗? : 那个题是已知k,求第k个permutation。
|