［ LeetCode］ Next Permutation（又是我 TAT……已哭晕）

[whalegia]

自从开始做 LeetCode 心里就住了几十个小人在哭每一个都是做不对或者做不出来痛哭流涕滚去扒别人代码留在我心里的。
然后这次直接题目都看不懂了……TAT

原题：
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
我的理解是：
找出用同样数字排列里，刚好比输入大的那一个。

但是我看讨论里面有个人说：
1243 应该变成 1342。
但是比 1243 大的还有 1324 啊？？1324 还比 1342 小，为什么答案是 1342 而不是 1324？
同时这个人在讨论里也提到了，要把右半部分排一下序，1342不是很明显右边还没有排序吗？＝。＝
https://oj.leetcode.com/discuss/17631/share-my-python-code-and-explain-how-to-get-the-solution



我还在 github 上找了另一个答案，给的注释也是要
Find the largest l such that num[k] < num[l] (if k exists)
为什么不是
Find the smallest l but also required num[k] < num[l]
???

https://gist.github.com/whaleee/33ca952beb6a615b6589


/痛哭流涕退下

[tangdibupt]

可以这样想解法：
1. 寻找第一个 digit[i] < digit[i+1]，
2， 从Length-1到i+1, 寻找最小的满足digit[x]<digit[i]的值， 记录x,
3, sort x+1到Length-1， 获得next permutation。

[rrfeng]

用一个数组来排序，
从末位数字起，插入法插入排序数组

如果发现数字比排序数组中的最大数字小，那么就得到答案了：
按照下列顺序摆放数字：
未参与排序的部分不动，排序数组最大值，排序数字从小到大。

[whalegia]

@tangdibupt
我觉得，好像不是寻找第一个 digit[i] < digit[i+1]，而是寻找最靠右的 i ，并且满足digit[i] < digit[i+1] 这个条件吧？

然后我还想请问一下，1243 的 next permutation 到底应该是 1324 还是 1342 呀？？？

[jox]

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，我反正是没看懂。

[proudzhu]

@jox 我觉得描述没啥问题啊。有啥问题？

[jox]

@proudzhu 他说是lexicographically next greater permutation of numbers，如果按照这个描述，1243应该得到结果1324，要么是描述有问题，要么是给的例子有问题。

[jakwings]

「lexicographically」和字符串的比较有关，再查查 ASCII 表就知道数字是按 0 到 9 升序排列的，理解了这个就好理解其它了。

[proudzhu]

@jox 关键是问题的例子不是这个啊。
https://oj.leetcode.com/discuss/17631/share-my-python-code-and-explain-how-to-get-the-solution
讨论里的谁知道是对的还是错的。这个链接里代码是对的，1243得到结果就是1324，不是他说的1342，自己跑跑就知道了，吓了我一跳。。。

[proudzhu]

@jox PS：你们写都是直接在网页上写的吗，都不用本地 IDE？

[jox]

@proudzhu 我晕，我没去看这个问题，也没看那个python的代码，我以为lz说的是问题给的例子呢

[jox]

@proudzhu 我不使用leetcode，我一般都是需要什么算法的话直接去翻算法的资料，这个leetcode应该是为了方便应付找工作时候的“考试”，我暂时没有这种需求

[tangdibupt]

@whalegia
之前没表述清楚，第一个是从右算起。
另外，应该是1324