Problem
Given a list of integers, which denote a permutation.
Find the previous permutation in ascending order.
NoticeThe list may contains duplicate integers.
ExampleFor [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 Solutionpublic class Solution { public ArrayListpreviousPermuation(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; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/65982.html
摘要:從末位向前遍歷,假設(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...
摘要:我覺得雖然在里分類是,但其實(shí)是一道難題。思路如下搞一個(gè)哈希表,存儲(chǔ)數(shù)組中每一位的后面小于它的數(shù)的個(gè)數(shù)。與上一題的不同之處時(shí)會(huì)有重復(fù)的數(shù)。當(dāng)然,每個(gè)重復(fù)數(shù)的都要階乘,例如有個(gè),個(gè),就是。是所有排列的次數(shù)和,返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...
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. ...
摘要:做法先把這個(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...
摘要:已獲原作者授權(quán)原系列地址游戲本章我們演示一個(gè)進(jìn)階例子我們用編寫了游戲這個(gè)游戲也被稱作或者或者是一個(gè)古老的益智解謎游戲由兩名玩家參與早在世紀(jì)人們就在用鉛筆和紙來玩這個(gè)游戲了在年發(fā)明的游戲正是受到這個(gè)游戲的啟發(fā)和在基本理念上是一樣的但被盒裝出售 已獲原作者授權(quán). 原系列地址: Python Tkinter Mastermind 游戲 本章我們演示一個(gè)進(jìn)階例子. 我們用 Tkinter 編...
閱讀 3717·2021-10-11 10:59
閱讀 1301·2019-08-30 15:44
閱讀 3479·2019-08-29 16:39
閱讀 2888·2019-08-29 16:29
閱讀 1800·2019-08-29 15:24
閱讀 808·2019-08-29 15:05
閱讀 1264·2019-08-29 12:34
閱讀 2302·2019-08-29 12:19