LintCode-51PreviousPermutation


题目:

给定一个整数数组来表示排列,找出其上一个排列。

样例:

给出排列[1,3,2,3],其上一个排列是[1,2,3,3]

给出排列[1,2,3,4],其上一个排列是[4,3,2,1]

要点1:什么是上一个排列呢?这里指的是全排列中从小到大排列的集合中的上一个。举个例子,123的全排列有123,132,213,231,312,321。那么231的上一个排列就是213.

要点2:考虑到数列中存在相同的数字

思路:

从后向前,依次比较后者是否比前者大,直到不满足条件,记录位置i,将此位置之后的所有 数倒序(意思就是找出后面这些数最大的排列组合),从i开始向后一次与i-1比较大小,如果比i大 则向后移动一位再与i-1比较,直到找到比i小的那一位,然后交换这一位与i-1的位置(理解成借位)

代码如下所示:

import java.util.List;

public class J51_PreviousPermutation {

    /**
     * 思路:从后向前,依次比较后者是否比前者大,直到不满足条件,记录位置i,将此位置之后的所有
     * 数倒序(意思就是找出后面这些数最大的排列组合),从i开始向后一次与i-1比较大小,如果比i大
     * 则向后移动一位再与i-1比较,直到找到比i小的那一位,然后交换这一位与i-1的位置(理解成借位)
     * @param num
     * @return
     */
    public List<Integer> run(List<Integer> num){

        if (num.size()!=1){

            int len = num.size();
            int i = len-1;
            while(i>0 && num.get(i)>=num.get(i-1)){
                i--;
            }
            num = ReverseList(num,i,len-1);
            if (i != 0){
                int j = i;
                while (num.get(j) >= num.get(i-1)){
                    j ++;
                }
                num = SwapItem(num,i-1,j);
            }

        }

        return num;
    }

    /**
     * 将num从i到j位置倒序
     * @param num
     * @param i
     * @param j
     * @return
     */
    private List<Integer> ReverseList(List<Integer> num, int i , int j){
        while(i<j){
            num = SwapItem(num,i,j);
            i++;
            j--;
        }
        return num;
    }

    /**
     * 交换num中第i和j位置的value
     * @param num
     * @param i
     * @param j
     * @return
     */
    private List<Integer> SwapItem(List<Integer> num, int i, int j){
        if (i < j){
            int tmp = num.get(i);
            num.set(i,num.get(j));
            num.set(j,tmp);
        }
        return num;
    }

}

分享博文


评论博文


Last one :   Win10安装TensorFlow1.9-GPU版本

Next article :   LintCode-211StringPermutation