本文共 2227 字，大约阅读时间需要 7 分钟。
题目：给出一个正整数，寻找全排列的下一个整数
思路：字典数算法。尽量保持高位不变，低位在最小范围内变换顺序。变换顺序的范围大小，取决于当前整数的逆序区域。步骤： 1、从后向前查看逆序区域，找到逆序区域的前一位，也就是数组置换的边界 2、让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置 3、把原来的逆序区域调整为顺序状态时间复杂度：3个步骤中的时间复杂度都是O(n),所以整体复杂度是O(n)/** * 题目：给出一个正整数，寻找全排列的下一个整数 * 思路：字典数算法。尽量保持高位不变，低位在最小范围内变换顺序。变换顺序的范围大小，取决于当前整数的逆序区域。 * 步骤： * 1、从后向前查看逆序区域，找到逆序区域的前一位，也就是数组置换的边界 * 2、让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置 * 3、把原来的逆序区域调整为顺序状态 ** 时间复杂度：3个步骤中的时间复杂度都是O(n),所以整体复杂度是O(n) */public class FindNearestNumber { public static int[] getFindNearestNumber(int[] array) { //1、从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界 int index = findTransferPoint(array); //如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字组成的整数，返回null if (index == 0) { return null; } //2、让逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置 //复制并入参，避免直接修改入参 int[] arrayCopy = Arrays.copyOf(array, array.length); exchangeHead(arrayCopy, index); //3、把原来逆序区域调整为顺序 reverse(arrayCopy, index); return arrayCopy; } private static int findTransferPoint(int[] array) { for (int i = array.length - 1; i > 0; i--) { if (array[i] > array[i - 1]) { return i; } } return 0; } private static void exchangeHead(int[] array, int index) { int head = array[index - 1]; for (int i = array.length - 1; i > 0; i--) { if (head < array[i]) { array[index - 1] = array[i]; array[i] = head; break; } } } private static void reverse(int[] array, int index) { for (int i = index; i < array.length - 1; i++) { if (array[i] > array[i + 1]) { int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } public static void main(String[] args) { int[] array = new int[]{1, 2, 3, 4, 5}; //打印12345后的10个全排列整数 for (int i = 0; i < 10; i++) { array = getFindNearestNumber(array); outputNumbers(array); } } /** * 输出数组 */ private static void outputNumbers(int[] array) { for (int i : array) { System.out.print(i); } System.out.println(); }}
转载地址：http://oqsvi.baihongyu.com/