小学生都能看懂的题解 | #没有重复项数字的全排列#

没有重复项数字的全排列

https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1

问题说明

我们需要找出一个数组中所有可能的顺序排列。例如,给定数组 [1, 2, 3],我们需要找出所有可能的排列组合:

  • [1, 2, 3]
  • [1, 3, 2]
  • [2, 1, 3]
  • [2, 3, 1]
  • [3, 1, 2]
  • [3, 2, 1]

解决方案

我们可以像玩拼图一样,一步一步地尝试不同的数字组合。想象你有一盒数字卡片,每次选择一张卡片放在一个空位上,直到所有的卡片都被用完为止。

步骤分解

  1. 创建一个空的排列组合列表
  2. 用来存放所有可能的排列组合。
  3. 创建一个临时列表
  4. 用来记录当前正在构建的排列。
  5. 递归地尝试所有可能性
  6. 如果当前排列已经包含了所有的数字,那么就把它添加到排列组合列表中。
  7. 否则,遍历数组中的每一个数字:如果这个数字还没有被用过,那么就把它加入到当前排列中。
  8. 然后继续递归地尝试剩下的数字。
  9. 当返回时,把刚才加入的数字移除,恢复原状。

代码实现

现在让我们用 Java 代码来实现这个过程:

import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 创建一个临时列表来记录当前排列
        ArrayList<Integer> tempList = new ArrayList<>();
        // 调用递归函数来生成排列
        generatePermutations(result, tempList, num);
        return result;
    }

    private void generatePermutations(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tempList, int[] num) {
        if (tempList.size() == num.length) {
            // 如果当前排列已经包含了所有数字,就把它添加到结果列表中
            result.add(new ArrayList<>(tempList));
        } else {
            // 遍历数组中的每一个数字
            for (int i = 0; i < num.length; i++) {
                // 如果这个数字还没有被用过
                if (!tempList.contains(num[i])) {
                    // 把这个数字加入到当前排列中
                    tempList.add(num[i]);
                    // 继续尝试下一个数字
                    generatePermutations(result, tempList, num);
                    // 回溯:移除刚刚加入的数字,恢复原状
                    tempList.remove(tempList.size() - 1);
                }
            }
        }
    }
}

如果这篇文章对你有帮助,请点个免费的赞👍,让它能够帮助更多的人。

#题解#
小学生都能看懂的算法 文章被收录于专栏

主要面向小白的算法文章。以小学生都能看懂为目标而编写,顺便巩固下自己。

全部评论

相关推荐

object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
shtdbb_:还不错,没有让你做了笔试再挂你
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务