實現獲取下一個排列的函數，算法需要將給定數字序列重新排列成字典序中下一個更大的排列。

如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列）。

必須原地修改，只允許使用額外常數空間。

以下是一些例子，輸入位于左側列，其相應輸出位于右側列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

?

?

分析：

這道題如果暴力解法的話，需要將可能的排列都寫出來，并且用數組存儲起來，不論是時間復雜度，亦或是空間復雜度都是不客觀的。

可以通過一次遍歷完成，從后向前遍歷

如果后面的值一直比前面與他相鄰的值大，那就說明目前的排序已經是最大值，我們按照題目需求，逆置數組即可

例如：7654321，965

如果后面的值比前面的值大時，將前面這個位置記錄下來，可以用x來表示，之后，將x后面的所有值中大于x但是最接近x的值與x進行交換。

例如：115->151? 4756->4765

但是這里有一個問題，對于一些排列無法得到想要的結果

例如：1765432->2765431 ,可以看到比1765432大的下一個數字應該是2176543，明顯得到了錯誤的答案

因此我們需要加一步操作，在交換之后，對x之后的元素進行一次排序，使之變為升序排序

?

代碼如下：

import java.util.Arrays;

public class Solution31 {
?? ?public static void nextPermutation(int[] nums) {
?? ??? ?int i,j,t,flag=0,min,k=0;? //flag是用來記錄當前序列是否為最大的序列，如果是其值為0，反之為1
?? ??? ?int n = nums.length;
?? ??? ?for(i=n-1;i>=1;i--)
?? ??? ?{
?? ??? ??? ?if(nums[i]>nums[i-1])
?? ??? ??? ?{
?? ??? ??? ??? ?flag = 1;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ?
?? ??? ?}
?? ??? ?if(flag==1)
?? ??? ?{
?? ??? ??? ?min = nums[i];
?? ??? ??? ?k = i;? ? ? ? ? ??
?? ??? ??? ?for(j=i;j<n;j++)
?? ??? ??? ?{
?? ??? ??? ??? ?if(nums[j]<min&&nums[j]>nums[i-1])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?min = nums[j];
?? ??? ??? ??? ??? ?k = j;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?t = nums[i-1];
?? ??? ??? ?nums[i-1] = nums[k];
?? ??? ??? ?nums[k] = t;
?? ??? ??? ?Arrays.sort(nums, i, nums.length);
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?for(i=0;i<n/2;i++)
?? ??? ??? ?{
?? ??? ??? ??? ?t = nums[i];
?? ??? ??? ??? ?nums[i] = nums[n-i-1];
?? ??? ??? ??? ?nums[n-i-1] = t;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?System.out.println(nums[i]);
?? ??? ?}
? ? }

?? ?public static void main(String[] args)
?? ?{
?? ??? ?//int[] nums = {1,1,5};
?? ??? ?//int[] nums = {3,2,1};
?? ??? ?//int[] nums = {1,2,3};
?? ??? ?//int[] nums = {1,3,2};
?? ??? ?//int[] nums = {1,7,6,5,4,3,2};
?? ??? ?//int[] nums = {2,3,1};
?? ??? ?int[] nums = {5,4,7,5,3,2};
?? ??? ?nextPermutation(nums);
?? ?}
}
?

總結

以上是生活随笔為你收集整理的Leetcode--31. 下一个排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。