当前位置：首页 > news >正文

全排列的 Java 实现

news 来源：原创 2024/9/20 18:29:38

引言

LeetCode 是一个流行的在线判题平台，提供了大量算法题目。其中的第46题“全排列”是一个经典的问题，要求生成一个给定数字的所有可能排列。这个问题可以通过回溯算法来解决。本文将介绍如何使用 Java 解决这个问题。

题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
]

问题分析

全排列问题是一个典型的回溯问题。我们需要生成所有可能的数字排列，并且每个排列都是由原序列中的数字组成，但顺序不同。

算法选择

对于全排列问题，回溯算法是非常自然且高效的解决方案。回溯算法的基本思想是：

从左到右依次选择一个数字放入当前位置。
固定当前位置的数字，递归地填充下一个位置。
当所有位置都被填满后，将当前的排列添加到结果中。
回溯，撤销上一步的选择，为当前位置选择下一个可能的数字。

Java 实现

以下是使用 Java 解决这个问题的代码实现：

import java.util.ArrayList;
import java.util.List;public class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(nums, result, new ArrayList<>(), nums.length);return result;}private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> tempList, int n) {if (tempList.size() == n) {result.add(new ArrayList<>(tempList));return;}for (int i = 0; i < n; i++) {// 检查是否已经使用过 nums[i]if (!tempList.contains(nums[i])) {tempList.add(nums[i]);backtrack(nums, result, tempList, n);tempList.remove(tempList.size() - 1); // 回溯}}}public static void main(String[] args) {Solution solution = new Solution();int[] nums = {1, 2, 3};List<List<Integer>> permutes = solution.permute(nums);System.out.println(permutes);}
}

代码解释

permute 方法：这是主方法，接收一个整数数组 nums。
backtrack 方法：这是一个递归方法，用于实现回溯算法。
- nums：原始数字数组。
- result：存储所有排列的列表。
- tempList：当前正在构建的排列。
- n：数组 nums 的长度。
回溯逻辑：如果 tempList 的大小等于 n，则将 tempList 添加到结果中。否则，遍历数组 nums，对于每个未使用的数字，将其添加到 tempList 中，并递归调用 backtrack 方法。