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 的大作中提到】
: 这个是一个排列组合题
: 给你一个数字
: 问，你用这些数字能组合出多少个比这个数字更小的数
|
p*****2
发帖数: 21240 | 4
Leetcode上有这道题吧？
【在 b****g 的大作中提到】
: 一串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 的大作中提到】
:
: Leetcode上有这道题吧？
|
p*****2
发帖数: 21240 | 6
leetcode上的是要简单一些。
【在 r**h 的大作中提到】
: 这题首先就应该把数字转换成字符串吧？
: leetcode上的那道题没有重复的元素，要简单一些呀
: （不过那题要写对感觉也不简单啊)
|
b****g
发帖数: 192 | 7 你是说Permutation Sequence那道题吗？
那个题是已知k，求第k个permutation。
【在 p*****2 的大作中提到】
:
: leetcode上的是要简单一些。
|
p*****2
发帖数: 21240 | 8
意思差不多吧？
【在 b****g 的大作中提到】
: 你是说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 的大作中提到】
:
: 意思差不多吧？
|
p*****2
发帖数: 21240 | 10
复杂度有点高吧？N!吧。
【在 b****g 的大作中提到】
: 我问的题是：已知某个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 的大作中提到】
:
: 复杂度有点高吧？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 的大作中提到】
: 没错！
: 所以我才来请教大家啊！！！
|
b****g
发帖数: 192 | 13 我想明白了，和leetcode的Permutation Sequence思路一样
一半一半的找。
每次都找一个阶乘那么多。
【在 p*****2 的大作中提到】
:
: 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 的大作中提到】
: 你是说Permutation Sequence那道题吗？
: 那个题是已知k，求第k个permutation。
|
