1
tangdibupt 2014-12-05 09:45:17 +08:00 1
可以这样想解法:
1. 寻找第一个 digit[i] < digit[i+1], 2, 从Length-1到i+1, 寻找最小的满足digit[x]<digit[i]的值, 记录x, 3, sort x+1到Length-1, 获得next permutation。 |
2
rrfeng 2014-12-05 10:09:49 +08:00 1
用一个数组来排序,
从末位数字起,插入法插入排序数组 如果发现数字比排序数组中的最大数字小,那么就得到答案了: 按照下列顺序摆放数字: 未参与排序的部分不动,排序数组最大值,排序数字从小到大。 |
3
whalegia OP @tangdibupt
我觉得,好像不是寻找第一个 digit[i] < digit[i+1],而是寻找最靠右的 i ,并且满足digit[i] < digit[i+1] 这个条件吧? 然后我还想请问一下,1243 的 next permutation 到底应该是 1324 还是 1342 呀??? |
4
jox 2014-12-05 13:22:26 +08:00 1
1243的下一个字典序是1324没错的,这道题描述的有问题,如果按照这道题的描述,例子1243应该得到结果1324.
算法: 1. 从右向左扫描,找到第一个i满足条件: num[i] > num[i - 1],如果找不到,那么当前序列就是最大序列,直接翻转得到结果 2. 从右向左扫描,找到第一个j满足条件:num[j] > num[i - 1],这个j一定存在,因为num[i]就大于num[i - 1] 3. num[j]和num[i - 1] 互换位置 4. 翻转从i到最后一个数字的序列得到结果 你给的那个python的算法自己都解释不清,他说sort right,结果也没sort right,我反正是没看懂。 |
6
jox 2014-12-05 13:53:07 +08:00 1
@proudzhu 他说是lexicographically next greater permutation of numbers,如果按照这个描述,1243应该得到结果1324,要么是描述有问题,要么是给的例子有问题。
|
7
jakwings 2014-12-05 13:58:48 +08:00 1
「lexicographically」和字符串的比较有关,再查查 ASCII 表就知道数字是按 0 到 9 升序排列的,理解了这个就好理解其它了。
|
8
proudzhu 2014-12-05 14:11:26 +08:00 1
@jox 关键是问题的例子不是这个啊。
https://oj.leetcode.com/discuss/17631/share-my-python-code-and-explain-how-to-get-the-solution 讨论里的谁知道是对的还是错的。这个链接里代码是对的,1243得到结果就是1324,不是他说的1342,自己跑跑就知道了,吓了我一跳。。。 |
11
jox 2014-12-05 14:19:45 +08:00 1
@proudzhu 我不使用leetcode,我一般都是需要什么算法的话直接去翻算法的资料,这个leetcode应该是为了方便应付找工作时候的“考试”,我暂时没有这种需求
|
12
tangdibupt 2014-12-05 14:42:17 +08:00 1
|