[LintCode] Previous Permutation

Pines_Cheng 发布于2019-08-14 15:44 / 3343人阅读

Problem

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Notice

The list may contains duplicate integers.

Example

For [1,3,2,3], the previous permutation is [1,2,3,3]

For [1,2,3,4], the previous permutation is [4,3,2,1]

Note Solution

public class Solution {
    public ArrayList previousPermuation(ArrayList nums) {
        int pre = nums.size()-1;
        while (pre > 0 && nums.get(pre-1) <= nums.get(pre)) pre--;
        pre--;
        if (pre >= 0) {
            int cur = pre+1;
            while (cur < nums.size() && nums.get(cur) < nums.get(pre)) cur++;
            cur--;
            int temp = nums.get(cur);
            nums.set(cur, nums.get(pre));
            nums.set(pre, temp);
        }
        int left = pre+1;
        int right = nums.size()-1;
        while (left < right) {
            int temp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, temp);
            left++;
            right--;
        }
        return nums;
    }
}

GPU云服务器云服务器 Previous Permutation LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65982.html

[LintCode] Next Permutation II [Next Permutation]

摘要：从末位向前遍历，假设循环开始全是倒序排列，如当第一次出现正序的时候，如的和此时从数列末尾向前循环到，找到第一个比大的交换这两个数，变成倒置第位到末位的数为正序排列这里的是完全倒置的排列，如，即上面循环的情况完全没有出现， Problem Implement next permutation, which rearranges numbers into the lexicographic...

mikasa 2019-08-14 15:15 评论0 收藏0
[LintCode] Permutation Index I & Permutation I

摘要：我觉得虽然在里分类是，但其实是一道难题。思路如下搞一个哈希表，存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然，每个重复数的都要阶乘，例如有个，个，就是。是所有排列的次数和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 评论0 收藏0
[LintCode] Permutation in String

Problem Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first strings permutations is the substring of the second string. ...

wenshi11019 2019-08-15 18:16 评论0 收藏0
[LintCode] Permutation Sequence

摘要：做法先把这个数放入一个数组里，同时计算出的阶乘。假设这一组是第组，第一个数就是，同时删去这个数，并让除以取余作为新的。如此循环，这样，下一组的成员数减少了，要找的位置也更为精确了。 Problem Given n and k, return the k-th permutation sequence. Example For n = 3, all permutations are li...

Jacendfeng 2019-08-14 15:19 评论0 收藏0
[译][Tkinter 教程13] Mastermind 游戏

摘要：已获原作者授权原系列地址游戏本章我们演示一个进阶例子我们用编写了游戏这个游戏也被称作或者或者是一个古老的益智解谜游戏由两名玩家参与早在世纪人们就在用铅笔和纸来玩这个游戏了在年发明的游戏正是受到这个游戏的启发和在基本理念上是一样的但被盒装出售已获原作者授权. 原系列地址: Python Tkinter Mastermind 游戏本章我们演示一个进阶例子. 我们用 Tkinter 编...

Jaden 2019-07-30 16:08 评论0 收藏0