Introduction
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
Input
第一行给出整数个数n，第二行给出n个排列整数
Output
输出将给定数字序列重新排列成字典序中下一个更大的排列
Sample
input
3 1 2 3
output
1 3 2
Solution
import java.util.Arrays; import java.util.Scanner; public class Main3 { public static void main(String[] args) { Scanner s=new Scanner(System.in); int nn=s.nextInt(); int[] nums=new int[nn]; for(int i=0;i<nn;i++){ nums[i]=s.nextInt(); } if (nums == null || nums.length == 0) return; int firstIndex = -1; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { firstIndex = i; break; } } if (firstIndex == -1) { reverse(nums, 0, nums.length - 1); System.out.print(nums[0]); for(int i=1;i<nn;i++){ System.out.print(" "+nums[i]); } return; } int secondIndex = -1; for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] > nums[firstIndex]) { secondIndex = i; break; } } swap(nums, firstIndex, secondIndex); reverse(nums, firstIndex + 1, nums.length - 1); System.out.print(nums[0]); for(int i=1;i<nn;i++){ System.out.print(" "+nums[i]); } } public static void reverse(int[] nums, int i, int j) { while (i < j) { swap(nums, i++, j--); } } public static void swap(int[] nums, int i, int i1) { int tmp = nums[i]; nums[i] = nums[i1]; nums[i1] = tmp; } }
Experience
这道题目认真考虑起来其实有点复杂。关键是怎么想的就把代码进行实现。
