資訊專欄INFORMATION COLUMN
摘要：邊界條件，這時(shí)候之后只有一個(gè)值數(shù)組一直遞減，這時(shí)候變成，沒(méi)有，只需要從到的所有數(shù)。
31. Next Permutation
題目鏈接：https://leetcode.com/problems...
這道題就是找規(guī)律，可以看出來(lái)下一個(gè)permutation的規(guī)律是：從右往左掃，找到第一個(gè)滿足：nums[i-1] < nums[i]條件的，再找到從右到左第一個(gè)比nums[i-1]大的數(shù)，把它們swap，再把所有i-1之后的數(shù)字swap即可。邊界條件：1. i = nums.length - 1，這時(shí)候i-1之后只有一個(gè)值, 2. 數(shù)組一直遞減，這時(shí)候i變成0，沒(méi)有nums[i-1]swap，只需要swap從0到nums.length - 1的所有數(shù)。
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 1;
while(i > 0) {
if(nums[i-1] < nums[i]) break;
i--;
}
// i = 0, decreasing
if(i != 0) {
int j = nums.length - 1;
while(j >= 0) {
if(nums[j] > nums[i-1]) break;
j--;
}
swap(nums, i-1, j);
}
// swap all elements after i-1
int end = nums.length - 1;
while(i < end) swap(nums, i++, end--);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66639.html
摘要：我們所找到的這個(gè)元素就是排序需要改變的第一個(gè)元素。然后我們選取一個(gè)剛好大于此元素的數(shù)，與當(dāng)前元素進(jìn)行替換。并對(duì)后面的所有元素重新按照升序排列就可以得到最終的答案。 題目詳情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...
摘要：如果當(dāng)前數(shù)字代表的整數(shù)值已經(jīng)是所有排列組合中的最大值，則返回當(dāng)前數(shù)字組成的最小值?？墒沁@意味著大量無(wú)用的數(shù)字的生成和比較。一個(gè)數(shù)字中的各個(gè)位上的數(shù)如何調(diào)整順序才能獲得一個(gè)最小的更大值。其次，要保證移動(dòng)之后，高位以后的值為最小值。 題目要求 Implement next permutation, which rearranges numbers into the lexicographi...
摘要：比如我們很容易知道下一個(gè)數(shù)字是。從尾到頭找，第一段的部分出現(xiàn)。后面的部分就可以有更大的組合。這里是在遞減序列中找到下一個(gè)比大的數(shù)字，作為序列的頭。尾部的遞減序列變成遞增序列。 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation o...
摘要：從末位向前遍歷，假設(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 lexicographic...
摘要：因?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...
閱讀 664·2021-10-19 11:45
閱讀 1620·2021-09-30 09:48
閱讀 1608·2021-08-16 10:56
閱讀 917·2021-07-26 23:38
閱讀 3293·2019-08-30 13:15
閱讀 2693·2019-08-30 12:45
閱讀 1941·2019-08-29 12:14
閱讀 2293·2019-08-26 18:42
