关键词:
寻找全排列的下一个数
摘自漫画算法:
题目:给出一个正整数,找出这个正整数所有数字全排列的下一个树。说的通俗点就是在一个整数所包含数字的全部组合中,找到一个大于且仅大于原数的新整数。
例子:
- 如果输入12345,则返回12354
- 如果输入12354,则返回12435
- 如果输入12435,则返回12453
解题思路
在给出具体思路解法之前,先思考一个问题:由固定几个数字组成的整数,怎么排列最大?怎么排列最小?
解答:如果是固定的几个数字,在逆序排列的情况下值最大,在顺序排列的情况下值最小
例子:
给出1、2、3、4、5这几个数字。最大组合为54321,最小组合为12345。
给出整数12354,它包含的数字是1、2、3、4、5,如何找到这些数字全排列之后仅大于原数的新整数呢?
为了和原数接近,我们需要尽量保持高位不变,低位在最小的范围内变换顺序。至于变换顺序的范围大小,则取决于当前整数的逆序区域。
如图所示,12354的逆序区域是最后两位,仅看这两位已经是当前的最大组合。若想最接近原数,又比原数更大,必须从倒数第3位开始改变。
怎样改变呢?12345的倒数第3位是3,我们需要从后面的逆序区域中找到大于3的最小的数字,让其和3的位置进行互换。
如图:
互换后的临时结果是12453,倒数第3位已经确定,这个时候最后两位仍然是逆序状态。我们需要把最后两位转变为顺序状态,以此保证在倒数第3位数值为4的情况下,后两位尽可能小。
这样一来,就得到了想要的结果12435。
总结:以上思路看起来复杂,其实只要3个步骤:
- 从后向前查看逆序区域,找到逆序区域的前一位,也就是数字置换的边界。
- 让逆序区域的前一位和逆序区域中大于它的最小数字交换位置。
- 把原来的逆序区域转为顺序状态。
这种解法有一个“高大上”的名字:字典序算法。
代码实现
import java.util.Arrays;
/**
* 描述:寻找全排列的下一个树。
* <p>
* Create By ZhangBiao
* 2020/6/7
*/
public class RangeNextNumber
public static int[] findNearestNumber(int[] numbers)
// 1、从后向前查看逆序区域,找到逆序区域的前一位,也就是数字置换的边界
int index = findTransferPoint(numbers);
// 如果数字置换边界是0,说明整个数组已经逆序,无法得到更大的相同数字组成整数,返回null
if (index == 0)
return null;
// 2、把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
// 复制并入参,避免直接修改入参
int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
exchangeHead(numbersCopy, index);
// 3、把原来的逆序区域转为顺序
reverse(numbersCopy, index);
return numbersCopy;
private static int[] reverse(int[] num, int index)
for (int i = index, j = num.length - 1; i < j; i++, j--)
int temp = num[i];
num[i] = num[j];
num[j] = temp;
return num;
private static int[] exchangeHead(int[] numbers, int index)
int head = numbers[index - 1];
for (int i = numbers.length - 1; i > 0; i--)
if (head < numbers[i])
numbers[index - 1] = numbers[i];
numbers[i] = head;
break;
return numbers;
private static int findTransferPoint(int[] numbers)
for (int i = numbers.length - 1; i > 0; i--)
if (numbers[i] > numbers[i - 1])
return i;
return 0;
private static void outputNumbers(int[] numbers)
for (int i : numbers)
System.out.print(i);
System.out.println();
public static void main(String[] args)
int[] numbers = 1, 2, 3, 4, 5;
// 打印12345之后的10个全排列整数
for (int i = 0; i < 19; i++)
numbers = findNearestNumber(numbers);
outputNumbers(numbers);
常见的算法问题全排列(代码片段)
在我参加蓝桥杯时发现大多数问题都可以采用暴力破解所以这个时候我就想进行一下总结:关于全排列问题的通用解法,比如:(无重复全排列)(有重复的选取)(从N个数中选取m个数然后进行排列的问题)我这里尝试总结一... 查看详情
算法学习——递归和排列组合(代码片段)
排列组合三大问题:1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合1.打印n个数的全排列这个题实际上是可以直接用STL中的next_permutation()函数,代码如下:#include<bits/stdc++.h&... 查看详情
stl中的全排列实现(代码片段)
...快的求出全排列,而这两个函数的实现却不是依赖于搜索算法(dfs)的。分析:以next_permutation为例,数据以1,2,3,4,5为例,对于一个排列我们知道其按照从小到大排序后的结果就是字典序最小的一个排列,而对于它的下一个... 查看详情
java与算法之-数字全排列(代码片段)
全排列是指n个数(或其他字符)所有可能的排列顺序,例如123三个数字的全排列是123132213231312321那么问题来了,任意输入一个大于1的数字n,列出1-n这n个数字的全排列。如果尝试手动列举一下123的全排列,会发现通常我们会在头脑... 查看详情
模拟-bailian1833:排列(代码片段)
...题可以转化为求一个排列的下一个排列,在stl中有现成的算法next_permulation(),在这里我们考虑自己实现一下next_permulation。因为一个数集的全排列需要按照字典序升序排列,这就要求两个相邻的排列之间前缀尽可能重合度高,那... 查看详情
全排列ii(力扣第47题)(代码片段)
...:给定一个可包含重复数字的序列,返回所有不重复的全排列。示例:输入:[1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]分析: 这个题和全排列一的不同之处在于,它给定的一组元素含有重复的元素存在,那么我们进行深度递归搜索的时... 查看详情
数据结构与算法之深入解析n个数全排列的求解思路与算法示例(代码片段)
一、全排列I①题目描述给定一个不含重复数字,长度为N的数组nums,返回其所有可能的全排列,可以按任意顺序返回结果。示例1:输入:nums=[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例2:... 查看详情
回溯算法求关于排列有关问题(代码片段)
八皇后问题就是一个典型的全排列问题了,这个在有一篇博客已经写过了,但是今天想在这里对于排列问题来一个总结。排列问题主要涉及到以下几个方面:1.不带重复数的全排列2.带重复数的全排列3.有限个数的全排列(例如从... 查看详情
算法提高排列数(全排列)(代码片段)
问题描述 0、1、2三个数字的全排列有六种,按照字母序排列如下: 012、021、102、120、201、210 输入一个数n 求0~9十个数的全排列中的第n个(第1个为0123456789)。输入格式 一行,包含一个整数n输出格式 一行... 查看详情
全排列(代码片段)
全排列回溯算法之排列树一问题描述给出一串字符的全排列二问题分析采用回溯算法之排列树三代码实现packagebacktracking_perm;importjava.io.BufferedWriter;importjava.io.FileWriter;importjava.io.IOException;importjava.util.Arrays;importjava.util.LinkedList 查看详情
全排列算法的全面解析(代码片段)
...全排列是一个比较常见问题,如果是一个比较喜欢考算法的公司(貌似一些大公司都比较喜欢考算法),那么估计就会考察应聘者这个全排列的问题了(就算不让你编写完整代码,也会让你描述大致的思路... 查看详情
算法习题---字符串的全排序列(代码片段)
...,比如下图为1,2,3的排列枚举树,此树和我们这里介绍的算法完全一致;二:全排列实现思路(1)n个元素的全排列=(n-1个元素的全排列 查看详情
回溯算法(代码片段)
回溯算法回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但... 查看详情
算法----leetcode回溯系列问题题解(代码片段)
回溯法回溯1.什么是回溯?2.回溯法解决的问题3.回溯法的模板LeetCode题目列表组合问题77.组合216组合总和III17.电话号码的字母组合39.组合总和40.组合总和II分割问题131.分割回文串93.复原IP地址子集问题78.子集90.子集II排列问题46.全... 查看详情
算法----leetcode回溯系列问题题解(代码片段)
回溯法回溯1.什么是回溯?2.回溯法解决的问题3.回溯法的模板LeetCode题目列表组合问题77.组合216组合总和III17.电话号码的字母组合39.组合总和40.组合总和II分割问题131.分割回文串93.复原IP地址子集问题78.子集90.子集II排列问题46.全... 查看详情
经典算法题-基础-寻找二叉树的下一个节点(代码片段)
目录问题描述分析思路当前节点有右子树当前节点没有右子树,且是父节点的左孩子当前节点没有右子树,且是父节点的右孩子相关代码问题描述题目描述给定一个二叉树和其中的一个结点,请找出中序遍历中的下一个结点并且... 查看详情
算法-回溯回溯总结(代码片段)
什么是回溯在求解诸如八皇后、全排列等问题时,我们通常使用深度优先搜索dfs在解空间内搜索满足条件的解,dfs的搜索过程可以看做是在一棵搜索树上遍历的过程。例如,求数字[1,2,3]的全排列的搜索树如下:当我们搜索到树... 查看详情
算法设计:全排列算法代码实现(代码片段)
在上星期的算法设计课程的学习中,我们学习了两种全排列算法,该算法用于求出数组1,2,3,...,n的所有可能的排列,今天我们就来看看这个算法的具体代码实现。 1. 第一种算法第一种算法和我们现实生活中习惯的方法较... 查看详情