找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1711|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Next Permutation】-【刷题第一弹2014】

[复制链接]

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
发表于 9-30-2014 04:36 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 wyu277 于 10-1-2014 04:32 PM 编辑

Next Permuation:
leetcode 快速通道:
www.oj.leetcode.com/problems/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

回帖方式:

思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目: (选填)

=========点击传送门查看所有题目哟========
               汇总贴 传送门
=================================

思路:
这题主要是想求下一个只比原数大一点的permuation。
换句话说,就是rearrange这个数:
     a.使得这个数比原数大;
     b.这个新数与原数的differences尽可能的小。


对于(b)来说,尽量只rearrange低位有效位(LSD). 高位能不动就不动。
(NOTE: 简单的注释下,MSD和LSD。当然各位大神肯定比我清楚,这边注释下以防我写得太乱大家看不清楚)
MSD: Most Significant Digit, 十进制,最高有效位。类似于Most Significant Bit
LSD : Least Significant Digit, 同上,最低有效位。

那我们就从低数位开始看,from end to top.


回到(a)怎么才能把一个数变大,或者说怎么把某一位(digit)变大。
没错,找一个比当前digit大的数swap一下。
找哪一位(digit)来换呢?
假设, 从左边的MSD中找一位换,那MSD那位就变小了,整个数就又小了。 (这也正好符合之前说的高位能不动就不动)
那我们只能从右边的LSD里找一个比当前位大的数交换。


那什么样的数可以变通过这样的方法变大呢?
或者说,什么样的数不可以通过这样的方法变大呢?
Remeber! Most of cases, flip the coin when you stuck.
这个简单,如果右边的数都小于当前digit的时候。


如上图,如果从右边向左扫描。找到可换的数位。
如果 i 比 i-1 小或者等于的时候:
            说明右边的数都是 从右向左的递增←,比i-1 (高位)都小。这就是不可以换的情况。
除外:
            说明右边肯定存在一个数大于  i-1(高位)。

找到那个刚好大当前位一点的数,对于右边已经是降序排列的,找起来就不用说啦。

最后就是特殊情况的要求,如果不可能rearrange就,resort成就小数。

[code]public void nextPermutation(int[] num) {    // special cases
    if (num==null||num.length<2)    return;

    int i=num.length-1;
    // find modified target position
    while (i>0&&num<=num[i-1]) i--;

    // if there is a available rearrange point
    if (i>0) {
        int j=num.length-1;
        // find the proper digit and swap it
        while (j>=i&&num[j]<=num[i-1]) j--;
        swap(num,i-1,j);
    }

    // resort the right part to smallest number
    sort(num,i);
}

static void swap(int[] A,int i,int j) {
    int temp = A;
    A = A[j];
    A[j] = temp;
}

static void sort(int[] A,int i) {
    int j=A.length-1;
    while (i         swap(A,i++,j--);
    }
}[/code]

复杂度: 时间复杂度当然是O(n),因为要求是in-place空间复杂度为O(1)

相似题目:  Permutaion Sequence                Permutation I, II

本帖被以下淘专辑推荐:

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
 楼主| 发表于 9-30-2014 04:44 PM | 显示全部楼层
本帖最后由 wyu277 于 9-30-2014 04:48 PM 编辑

代码贴的有问题,我会重新排版的。
回复 支持 反对

使用道具 举报

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 10-23-2014 11:30 PM | 显示全部楼层
赞分析,楼主还拿小黑板写真是够花心思!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表