[LintCode] Previous Permutation

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

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

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

轉載請注明本文地址：http://m.hztianpu.com/yun/65982.html

[LintCode] Next Permutation II [Next Permutation]

摘要：從末位向前遍歷，假設循環(huán)開始全是倒序排列，如當?shù)谝淮纬霈F(xiàn)正序的時候，如的和此時從數(shù)列末尾向前循環(huán)到，找到第一個比大的交換這兩個數(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ù)組中每一位的后面小于它的數(shù)的個數(shù)。與上一題的不同之處時會有重復的數(shù)。當然，每個重復數(shù)的都要階乘，例如有個，個，就是。是所有排列的次數(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

摘要：做法先把這個數(shù)放入一個數(shù)組里，同時計算出的階乘。假設這一組是第組，第一個數(shù)就是，同時刪去這個數(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 游戲

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

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