请教一道Leetcode 题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道Leetcode 题

请教一道Leetcode 题# JobHunting - 待字闺中

f*m2012-06-11 07:06

1 楼

说实话，没太看懂题。。。
Next Permutation
Implement next permutation, which rearranges numbers into the
lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest
possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its
corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

h*e2012-06-11 07:06

2 楼

不懂在什么地方？举例如下：
123->132->213->231->312->321->123->...
111->111->...
C++ STL里就有一个next_permutation的函数。

【在 f*********m 的大作中提到】

: 说实话，没太看懂题。。。
: Next Permutation
: Implement next permutation, which rearranges numbers into the
: lexicographically next greater permutation of numbers.
: If such arrangement is not possible, it must rearrange it as the lowest
: possible order (ie, sorted in ascending order).
: The replacement must be in-place, do not allocate extra memory.
: Here are some examples. Inputs are in the left-hand column and its
: corresponding outputs are in the right-hand column.
: 1,2,3 → 1,3,2

y*g2012-06-11 07:06

3 楼

就是字母顺序全排列，求下一个，
比如 123的全排列是
123, 132, 213, 231, 312, 321
那么给input 123，就输出132
给213就输出 231
基本类似c++的next_permutation

【在 f*********m 的大作中提到】

f*m2012-06-11 07:06

4 楼

哦，多谢，我再试试

p*22012-06-11 07:06

5 楼

def next_permutation(l):
i=len(l)-2
while i>=0:
if l[i]break
i-=1

if i>=0:
j=i+1
while jif(l[j]break
j+=1
j-=1
l[i],l[j]=l[j],l[i]

l[i+1:len(l)]=reversed(l[i+1:len(l)])

f*m2012-06-11 07:06

6 楼

谢谢

E*02012-06-11 07:06

7 楼

Hi, Peking2. 你的算法看不懂。能不能comment一下？谢谢:)

【在 p*****2 的大作中提到】

: def next_permutation(l):
: i=len(l)-2
: while i>=0:
: if l[i]: break
: i-=1
:
: if i>=0:
: j=i+1
: while j

C*U2012-06-11 07:06

8 楼

有一个算法请大牛们指正
先看最后两位，通过交换看是不是得到了下一个
如果可以，那么就完成了
如果不可以，看最后三位
找出最后三位数字中比百位大一个数字放到百位，然后剩下的数字从小到大排列
三位数字也不行的话就选四位
例子
13652
首先看52，发现交换他们变小了，不是下一个，不行
然后看652，发现没有比6大的数字，说明也不行，
然后看3652,发现千位上的3后面有5比3大一个，（6比3大两个，因为有5），那么把5放
到千位上，然后后面排成236.
15236就是后一个permutation。
不知道这样有没有错哦

【在 f*********m 的大作中提到】

n*m2012-06-11 07:06

9 楼

有道理。
综合一下你的逻辑，
从最后两位开始循环，
如果数列从大到小排着，把指针调前一位；
如果不是从大到小，找出比第一位大但大的最少的数，变成第一位，其余数字排成最小
数既可。

【在 C***U 的大作中提到】

: 有一个算法请大牛们指正
: 先看最后两位，通过交换看是不是得到了下一个
: 如果可以，那么就完成了
: 如果不可以，看最后三位
: 找出最后三位数字中比百位大一个数字放到百位，然后剩下的数字从小到大排列
: 三位数字也不行的话就选四位
: 例子
: 13652
: 首先看52，发现交换他们变小了，不是下一个，不行
: 然后看652，发现没有比6大的数字，说明也不行，

w*22012-06-11 07:06

10 楼

1.先找到第一个不是持续递增的位置
2.找到之前数字里面最近一次超过它的数字（接下来一个数字小于它），和它swap
3.reverse除了第一个数字外的所有数字

【在 E*******0 的大作中提到】

: Hi, Peking2. 你的算法看不懂。能不能comment一下？谢谢:)

a*y2012-06-11 07:06

11 楼

上面说的基本正确，第二步里面应该还是从end开始找
bool _next_permutation(int* begin, int* end)
{
if (begin == end) return false;
int* x1 = end - 1;
while (x1 >= begin && *x1 >= *(x1+1)) --x1;
if (x1 == begin)
{
reverse(begin, end);
return false;
}
int* x2 = end;
while (*x2 < *x1) --x2;
swap(*x1, *x2);
reverse(x1+1, end);
return true;
}

m*k2012-06-11 07:06

12 楼

离散数学书标准算法，：－）
先每位排序，从最小开始，从左到右，
设当前处理位＝最后一位；
A：从当前处理位开始，向左扫描，找到数值比它小的一位i，交换，i 后边所有位排序
，从小到大，从左到右，重设当前处理位＝最后一位；若找不到数值比它小的，当前
处理位左移一位， go to A; 如果无法左移，done。
example：
123,
当前处理位＝最后一位，指向3, 向左扫描，找到比它小的一位，值是2，交换，得
132, 排序3后的所有位，
得132,
当前处理位重设为最后一位，
指向2,向左扫描，找到比它小的一位，值是1,交换得231,排序2后的所有位,得213,
当前处理位重设为最后一位，
指向3,向左扫描，找到比它小的一位，值是1, 交换得231，排序3后的所有位,仍得231,
当前处理位重设为最后一位，
指向1, 向左扫描，无法找到比它小的一位，当前处理位左移一位，指向3,
3,向左扫描，找到比它小的一位，值是2, 交换得321，排序3后的所有位，得312,
当前处理位重设为最后一位，
指向2，向左扫描，找到比它小的一位，值是1,交换得321,排序2后的所有位，得321,
当前处理位重设为最后一位，
指向1,
向左扫描，无法找到比1小的一位，
当前处理位左移一位，指向2,
向左扫描，无法找到比2小的一位，
当前处理位左移一位，指向3,
向左扫描，无法找到比3小的一位，
无法左移，done。（就本题而言，done 可以换成 reverse）

【在 C***U 的大作中提到】

b*d2012-06-11 07:06

13 楼

当年看nextPermutation的时候，就觉得这个题要是面试，除非是事前知道答案，不然
不可能当场做出来。我去查wiki，记得是一片paper，专门说这个算法。
面试测算法的话，用这个题，不是个好例子，对方肯定是坏人。。

p*22012-06-11 07:06

14 楼

这道题做出来还是有可能的吧？当然最优解不行。

【在 b*******d 的大作中提到】

: 当年看nextPermutation的时候，就觉得这个题要是面试，除非是事前知道答案，不然
: 不可能当场做出来。我去查wiki，记得是一片paper，专门说这个算法。
: 面试测算法的话，用这个题，不是个好例子，对方肯定是坏人。。

p*22012-06-11 07:06

15 楼

我写了一个练练。
public void nextPermutation(int[] num)
{
int i=num.length-2;
while(i>=0 && num[i]>num[i+1])
i--;
if(i>0)
{
int j=num.length-1;
while(num[j]j--;
swap(num,i,j);
}
reverse(num,i+1,num.length-1);
}

l*a2012-06-11 07:06

16 楼

这个.length是field or method?
swap/reverse是库函数吗？
写全点让我们学习一下

【在 p*****2 的大作中提到】

: 我写了一个练练。
: public void nextPermutation(int[] num)
: {
: int i=num.length-2;
: while(i>=0 && num[i]>num[i+1])
: i--;
: if(i>0)
: {
: int j=num.length-1;
: while(num[j]

p*22012-06-11 07:06

17 楼

你现在不是搞Java吗？

【在 l*****a 的大作中提到】

: 这个.length是field or method?
: swap/reverse是库函数吗？
: 写全点让我们学习一下

c*p2012-06-11 07:06

18 楼

不用最优解怎么做？
可以把全排列都写出来，
然后写到给的这个array的时候，标记，到了下一个，输出？

【在 p*****2 的大作中提到】

:
: 你现在不是搞Java吗？

b*e2012-06-11 07:06

19 楼

How do you prove this algorithm is traversing all the permutations?

【在 p*****2 的大作中提到】

: def next_permutation(l):
: i=len(l)-2
: while i>=0:
: if l[i]: break
: i-=1
:
: if i>=0:
: j=i+1
: while j

r*h2012-06-11 07:06

20 楼

这题看似简单但是下标操作很绕人
要一次bug free相当不容易

c*p2012-06-11 07:06

21 楼

是算法太饶人了。
楼上有个起了误导作用。。。

【在 r**h 的大作中提到】

: 这题看似简单但是下标操作很绕人
: 要一次bug free相当不容易

D*a2012-06-11 07:06

22 楼

这个算法有点小问题。例如 1，3，4，2 将导致 2，1，3，4
我的算法是从右往左查找第一个不按升序排列的那个数，做个标记（我用的i-1），然
后在数列【i，last）从右往左找第一个比标记的数大的那个数，记为j，交换这两个
数，然后升序从新排列【i，last）。以下是实现
7 void NextPermutation (int num[], int SZ) {
8 int i=SZ-1, j=i;
9 while(i!=0) {
10 if(num[i-1]11 while(num[i-1]>=num[j])
12 j--;
13 int x=num[i-1];
14 num[i-1]=num[j];
15 num[j]=x;
16 sort(num+i,num+SZ);
17 break;
18 }
19 i--;
20 }
21 if(i==0) sort(num, num+SZ);
22 }

【在 m*****k 的大作中提到】

: 离散数学书标准算法，：－）
: 先每位排序，从最小开始，从左到右，
: 设当前处理位＝最后一位；
: A：从当前处理位开始，向左扫描，找到数值比它小的一位i，交换，i 后边所有位排序
: ，从小到大，从左到右，重设当前处理位＝最后一位；若找不到数值比它小的，当前
: 处理位左移一位， go to A; 如果无法左移，done。
: example：
: 123,
: 当前处理位＝最后一位，指向3, 向左扫描，找到比它小的一位，值是2，交换，得
: 132, 排序3后的所有位，

r*e2012-06-11 07:06

23 楼

贴个我的implementation吧：
void leetcode_nextPermutation(vector &num) {
int sz = num.size();
if (sz<=1) return;
vector::iterator prev=num.end(), next, pos=num.end();
--prev;
for (;;) {
next = prev--;
if (*prev < *next) {
while ((*prev >= *--pos));
iter_swap(prev, pos);
reverse(next, num.end());
return;
}
if (prev == num.begin()) {
reverse(num.begin(), num.end());//this is not needed to pass OJ but
that's how STL's version is implemented
return;
}
}
}