資訊專(zhuān)欄INFORMATION COLUMN
摘要：從末位向前遍歷，假設(shè)循環(huán)開(kāi)始全是倒序排列，如當(dāng)?shù)谝淮纬霈F(xiàn)正序的時(shí)候，如的和此時(shí)從數(shù)列末尾向前循環(huán)到，找到第一個(gè)比大的交換這兩個(gè)數(shù)，變成倒置第位到末位的數(shù)為正序排列這里的是完全倒置的排列，如，即上面循環(huán)的情況完全沒(méi)有出現(xiàn)，
Problem
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
ExampleHere are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
ChallengeThe replacement must be in-place, do not allocate extra memory.
Solutionpublic class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
if (nums == null || len == 0) return;
//從末位向前遍歷，（假設(shè)循環(huán)開(kāi)始全是倒序排列，如65321）
for (int i = len - 2; i >= 0; i--) {
//當(dāng)?shù)谝淮纬霈F(xiàn)正序的時(shí)候，如465321的4和6
if (nums[i] < nums[i+1]) {
//此時(shí)從數(shù)列末尾向前循環(huán)到i，
//找到第一個(gè)比nums[i]大的nums[j]
int j;
for (j = len - 1; j >= i; j--) {
if (nums[j] > nums[i]) break;
}
//交換這兩個(gè)數(shù)，變成564321
swap(nums, i, j);
//倒置第i+1位到末位的數(shù)為正序排列512346
reverse(nums, i+1, len-1);
return;
}
}
//這里return的是完全倒置的排列，如654321，
//即上面for循環(huán)的if情況完全沒(méi)有出現(xiàn)，for循環(huán)沒(méi)有做過(guò)任何操作
reverse(nums, 0, len-1);
return;
}
public void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
public void reverse(int[] A, int start, int end) {
while (left < right) swap(A, start++, end--);
}
}
public class Solution {
public void nextPermutation(int[] A) {
int n = A.length, i = n-2;
while (i >= 0 && A[i] >= A[i+1]) i--;
if (i >= 0) {
int j = n-1;
while (A[j] <= A[i]) j--;
swap(A, i, j);
}
reverse(A, i+1, n-1);
return;
}
public void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
public void reverse(int[] A, int i, int j) {
while (i < j) swap(A, i++, j--);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65494.html
摘要：解題思路這道題是要將排列按字典序排列，然后求出下一個(gè)排列，一種辦法是我們先求出所有的排序情況，但是題目規(guī)定不能占有額外空間。每次求出一個(gè)數(shù)字后，要及時(shí)的把它從中刪除掉。采用來(lái)構(gòu)造結(jié)果序列。 PermutationsGiven a collection of distinct numbers, return all possible permutations. For example, ...
摘要：我覺(jué)得雖然在里分類(lèi)是，但其實(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...
摘要：因?yàn)樵黾痈呶粫?huì)帶來(lái)更大的增益。所以對(duì)于一個(gè)長(zhǎng)為的序列，我們?cè)黾拥谖坏那疤崾?，前位已?jīng)達(dá)到了最大排列方法。因?yàn)槭钦蚁乱粋€(gè)數(shù)，所以我們要找一個(gè)比小卻盡可能大的數(shù)，所以找到。把換到的位置后，后三位仍然是個(gè)降序的排列。 Next Permutation Implement next permutation, which rearranges numbers into the lexicogr...
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 per...
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. ...
閱讀 2633·2019-08-30 10:53
閱讀 3233·2019-08-29 16:20
閱讀 2991·2019-08-29 15:35
閱讀 1817·2019-08-29 12:24
閱讀 2908·2019-08-28 18:19
閱讀 1897·2019-08-23 18:07
閱讀 2387·2019-08-23 15:31
閱讀 1232·2019-08-23 14:05
