Next Permutation
给一个数组, 求它的下一个组合顺序上的组合. 这个是个传统算法, 先从后往前找到一个递增的index. 如果没有, 证明已经是最后一个组合了, 直接反转全部数组即可. 如果有, 从前往后找到第一个比这个index上大的数, 然后swap这两个数, 并且把这个数index, 后边的剩下所有数都反转.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public class Solution { /** * @param num: an array of integers * @return: return nothing (void), do not return anything, modify num in-place instead */ public void reverse(int[] num, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { int temp = num[i]; num[i] = num[j]; num[j] = temp; } } public void nextPermutation(int[] num) { // find the last increase index int index = -1; for (int i = num.length - 2; i >= 0; i--) { if (num[i] < num[i + 1]) { index = i; break; } } if (index == -1) { reverse(num, 0, num.length - 1); return; } // find the first bigger one int biggerIndex = index + 1; for (int i = num.length - 1; i > index; i--) { if (num[i] > num[index]) { biggerIndex = i; break; } } // swap them to make the permutation bigger int temp = num[index]; num[index] = num[biggerIndex]; num[biggerIndex] = temp; // reverse the last part reverse(num, index + 1, num.length - 1); } } |