w***y
发帖数: 6251 | 1 就是这个题目
给一个整数，求next permutation 就是数字组成一样的 但是比这个数大的最小的一个数
我一开始想的方法是, 这个整数看做a_0...a_n, 找一对(i,j) , a[i] < a[j], j>i.
然后i尽量大, a[j]尽量小. 后来发现一个问题, 就是swap之后起码i之后的数字可
以重排小-->大, 会有一个更小的数字.
这个方法非常ad hoc, 但是我自己看半天又看不出问题. 大牛能指点一下么?
多谢啦! | g**********y
发帖数: 14569 | 2 http://wordaligned.org/articles/next-permutation#tocwhats-happe
个数
i.
【在 w***y 的大作中提到】
: 就是这个题目
: 给一个整数，求next permutation 就是数字组成一样的 但是比这个数大的最小的一个数
: 我一开始想的方法是, 这个整数看做a_0...a_n, 找一对(i,j) , a[i] < a[j], j>i.
: 然后i尽量大, a[j]尽量小. 后来发现一个问题, 就是swap之后起码i之后的数字可
: 以重排小-->大, 会有一个更小的数字.
: 这个方法非常ad hoc, 但是我自己看半天又看不出问题. 大牛能指点一下么?
: 多谢啦!
| c****p
发帖数: 6474 | 3 find the right most peak, switch the peak digit with the nearest and smaller
digit on its left. If no such left smaller digit can be found, then no
solution.
个数
i.
【在 w***y 的大作中提到】
: 就是这个题目
: 给一个整数，求next permutation 就是数字组成一样的 但是比这个数大的最小的一个数
: 我一开始想的方法是, 这个整数看做a_0...a_n, 找一对(i,j) , a[i] < a[j], j>i.
: 然后i尽量大, a[j]尽量小. 后来发现一个问题, 就是swap之后起码i之后的数字可
: 以重排小-->大, 会有一个更小的数字.
: 这个方法非常ad hoc, 但是我自己看半天又看不出问题. 大牛能指点一下么?
: 多谢啦!
| p*****2
发帖数: 21240 | 4 就是从右边开始找，每一个数字找右边比它大的一个数字，如果有几个选择最小的那个
，然后交换。如果找不到的话，就没有比它大的了。 | s******n
发帖数: 3946 | 5 find right most number and the nearest number on the left of it which is
smaller than it.
exchange the two numbers.
sort the numbers after the left one. | z*********8
发帖数: 2070 | 6 4,2,0,2,3,2,0 不work吧
这样会将第一个0与最后一个2交换， 而不是将3和最后一个2交换
我觉得应该是：
find right most number which has the farthest number on the RIGHT of it
which is GREATER than it.
【在 s******n 的大作中提到】
: find right most number and the nearest number on the left of it which is
: smaller than it.
: exchange the two numbers.
: sort the numbers after the left one.
| b***e
发帖数: 1419 | 7 Find k where k is the smallest number such that a[k..n] is a strictly
descending sequence.
If k == 0, then return null.
Otherwise, let j be the index such that a[j] is the smallest among a[k..n]
and a[j] > a[k-1]. Now the next number would be:
a[0..k-2], a[j], sort(a[k-1..j-1], a[j+1, n])
个数
i.
【在 w***y 的大作中提到】
: 就是这个题目
: 给一个整数，求next permutation 就是数字组成一样的 但是比这个数大的最小的一个数
: 我一开始想的方法是, 这个整数看做a_0...a_n, 找一对(i,j) , a[i] < a[j], j>i.
: 然后i尽量大, a[j]尽量小. 后来发现一个问题, 就是swap之后起码i之后的数字可
: 以重排小-->大, 会有一个更小的数字.
: 这个方法非常ad hoc, 但是我自己看半天又看不出问题. 大牛能指点一下么?
: 多谢啦!
|
|
