经典算法每日一练-第五十四天-没有重复项数字的全排列

日落3

计算机科学与技术

1，写在前面的话

朋友们，大家好！写经典算法刷题练习的笔记已经有一段时间了， 前段时间为了准备秋招面试和提高算法能力，开始了经典算法刷题的道路，这一写就一发不可收拾，这一段时间，自己的算法能力确实有了很明显的提高，自己肉眼可见，做算法题目的速度也变快了，思维方式也变得敏捷了很多，感谢这一段时间以来自己付出的努力！

天道酬勤，事虽难，做则可成，万事贵在坚持。 我决定坚持写自己的刷题笔记，用来提高自己的算法能力，同时监督自己每天都要进行经典算法的训练，同时也希望能能在这里帮助到大家，个人的感觉，在线刷题的方式训练算法能力真的很方便很高效。很多朋友最近都在问我关于提升自己的算法能力的方式方法， 这里给大家放上我平时训练算法题目的方法，身边学生朋友都在训练自己的算法能力的 ：点击了解刷题训练算法能力的方法！！ 还有，今天我们要练习的经典题目也在这里哦！！

今天要练习的经典算法题目是： 第五十四天-没有重复项数字的全排列

2，题目描述

给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

3，示例1

输入：[1,2,3]
返回值：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

4，示例2

输入：[1]
返回值：[[1]]

5，个人思路分析详解|仅供参考

刚才我们进行了详细的题目描述，同时，我们还提供了多个输入输出的示例，在线编程时，可以用来检测自己程序的正确性，下面我们就要梳理一下这道经典算法题目的实现思路，同时，我们还要梳理一下具体的实现步骤，然后，我们可以通过画图的方式更加深入的理解算法的内涵，在真正的理解算法的思路以后，我们就可以敲代码啦，此时，我们可以从Java和C++两个编程语言出发，不经训练算法能力，还能深入理解这两个编程语言的语法！！

接下来我们就开始美妙的算法之旅吧：

接下来，我们先来分析这道题目的思路，这里的个人思路仅供参考： 全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。

如何保证每个元素能和从自己开始后的每个元素都交换位置，这种时候我们可以考虑递归。为什么可以使用递归？我们可以看数组[1,2,3,4]，如果遍历经过一个元素2以后，那就相当于我们确定了数组到该元素为止的前半部分，前半部分1和2的位置都不用变了，只需要对3，4进行排列，这对于后半部分而言同样是一个全排列，同样要对从每个元素开始往后交换位置，因此后面部分就是一个 子问题 。那我们考虑递归的几个条件。

当然能使用多种算法解决这道题目对于训练算法能力也是很好的。完成了第一步梳理好了思路，接下来我们就要整理具体的解题步骤，然后我们再敲代码：

step 1：先将数组排序，获取字典序最小的排列情况。
step 2：递归的时候根据当前下标，遍历后续的元素，交换二者位置后，进入下一层递归。
step 3：处理完一分支的递归后，将交换的情况再换回来进行回溯，进入其他分支。
step 4：当前下标到达数组末尾就是一种排列情况。

我们已经对题目进行了比较深入的分析，接下来下一步就是画图，画图对于我们理解算法来说也是至关重要的：

现在我们已经完成了很重要的几个步骤，接下来我们就来一起敲代码吧！！

6，详细解题过程

完成了前面的算法思路分析，解题步骤分析，画图理解算法等步骤，现在终于可以自己动手敲代码了，首先打开我们前面介绍的真题就可以在线练习我们今天练习的经典算法题目了：

首先我们学习Java的时候，可以用Java来解决这个问题：

import java.util.*;
public class Solution {
    //交换位置函数
    private void swap(ArrayList<Integer> num, int i1, int i2{
        int temp = num.get(i1);
        num.set(i1, num.get(i2));
        num.set(i2, temp);
    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index){
        //分枝进入结尾，找到一种排列
        if(index == num.size() - 1){
            res.add(num);
        else{
            //遍历后续的元素
            for(int i = index; i < num.size(); i++){
                //交换二者
                swap(num, i, index);
                //继续往后找
                recursion(res, num, index + 1);
                swap(num, i, index);
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        //先按字典序排序
        Arrays.sort(num); 
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> nums = new ArrayList<Integer>();
        //数组转ArrayList