[LeetCode]31. Next Permutationjava

/**31. Next Permutation * @param nums */ public void nextPermutation(int[] nums) { int i=nums.length-1; for (; i>0; i--) { if (nums[i] > nums[i-1]) break; } if (i==0) { Arrays.sort(nums); } else { //找到比nums[i]的数 int change = nums[i-1]; int nextMax = nums[i]; int nextMaxIndex = i; for (int j=i+1; j<nums.length; j++) { if (nums[j] > change && nums[j] < nextMax) { nextMax = nums[j]; nextMaxIndex = j; } } //交换 int temp = change; nums[i-1] = nextMax; nums[nextMaxIndex] = temp; //排序 for (int m=i; m<nums.length; m++) { for (int n=m+1; n<nums.length; n++) { if (nums[m] > nums[n]) { temp = nums[m]; nums[m] = nums[n]; nums[n] = temp; } } } } }

这道题是给定一个数组和一个排列，求下一个排列。算法上其实没有什么特别的地方，主要的问题是经常不是一见到这个题就能马上理清思路。下面我们用一个例子来说明，比如排列是(2,3,6,5,4,1)，求下一个排列的基本步骤是这样： 1) 先从后往前找到第一个不是依次增长的数，记录下位置p。比如例子中的3，对应的位置是1; 2) 接下来分两种情况： (1) 如果上面的数字都是依次增长的，那么说明这是最后一个排列，下一个就是第一个，其实把所有数字反转过来即可(比如(6,5,4,3,2,1)下一个是(1,2,3,4,5,6)); (2) 否则，如果p存在，从p开始往后找，找找找，找到第一个比他小的数，然后两个调换位置，比如例子中的4。调换位置后得到(2,4,6,5,3,1)。最后把p之后的所有数字倒序，比如例子中得到(2,4,1,3,5,6), 这个即是要求的下一个排列。

改进

public void nextPermutation(int[] nums) { int len = nums.length; boolean flag = false; for (int i = len-1; i > 0; i--) { if (nums[i] > nums[i-1]) { //从i开始找到最小的那个 int n= findMin(nums, i-1, len-1); int temp = nums[i-1]; nums[i-1] = nums[n]; nums[n] = temp; sort(nums, i, len-1); flag = true; break; } } if (flag == false) { Arrays.sort(nums); } } public void sort(int[] nums, int s, int e) { for(int i = s; i <= e; i++) { for(int j = i+1; j <= e; j++) { if (nums[i] > nums[j]) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } } public int findMin(int[] nums, int s, int e) { int x = nums[s]; int n = s+1; for(int i = s+2; i <= e; i++) { if (nums[i] < nums[n] && nums[i] > x) { n = i; } } return n; }