[LintCode] Previous Permutation

Pines_Cheng 發(fā)布于2019-08-14 15:44 / 3352人閱讀

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;
    }
}

云服務(wù)器 GPU云服務(wù)器 Previous Permutation LintCode LintCode134_LRU

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65982.html

相關(guān)文章

[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設(shè)循環(huán)開始全是倒序排列，如當(dāng)?shù)谝淮纬霈F(xiàn)正序的時(shí)候，如的和此時(shí)從數(shù)列末尾向前循環(huán)到，找到第一個(gè)比大的交換這兩個(gè)數(shù)，變成倒置第位到末位的數(shù)為正序排列這里的是完全倒置的排列，如，即上面循環(huán)的情況完全沒有出現(xiàn)， Problem Implement next permutation, which rearranges numbers into the lexicographic...

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

摘要：我覺得雖然在里分類是，但其實(shí)是一道難題。思路如下搞一個(gè)哈希表，存儲數(shù)組中每一位的后面小于它的數(shù)的個(gè)數(shù)。與上一題的不同之處時(shí)會有重復(fù)的數(shù)。當(dāng)然，每個(gè)重復(fù)數(shù)的都要階乘，例如有個(gè)，個(gè)，就是。是所有排列的次數(shù)和，返回下一次。 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

摘要：做法先把這個(gè)數(shù)放入一個(gè)數(shù)組里，同時(shí)計(jì)算出的階乘。假設(shè)這一組是第組，第一個(gè)數(shù)就是，同時(shí)刪去這個(gè)數(shù)，并讓除以取余作為新的。如此循環(huán)，這樣，下一組的成員數(shù)減少了，要找的位置也更為精確了。 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 游戲

摘要：已獲原作者授權(quán)原系列地址游戲本章我們演示一個(gè)進(jìn)階例子我們用編寫了游戲這個(gè)游戲也被稱作或者或者是一個(gè)古老的益智解謎游戲由兩名玩家參與早在世紀(jì)人們就在用鉛筆和紙來玩這個(gè)游戲了在年發(fā)明的游戲正是受到這個(gè)游戲的啟發(fā)和在基本理念上是一樣的但被盒裝出售已獲原作者授權(quán). 原系列地址: Python Tkinter Mastermind 游戲本章我們演示一個(gè)進(jìn)階例子. 我們用 Tkinter 編...

Jaden 2019-07-30 16:08 評論0 收藏0