故事的主人公是个高校行政岗位的阿姨，工作了十年，按理说在体制内应该是铁饭碗了吧？结果，领导突然告诉她岗位要裁掉，让她提前写转岗申请书，找其他岗位。
阿姨挺天真地按照要求交了转岗申请，结果面试辅导员岗位也没通过，接着人事说没有二级学院接收她的意思——也就是说，根本没有岗位了。最后，人事建议她“自己提离职”，这可真是让人心酸了。
作为过来人，我觉得这种情况其实挺常见的，特别是对于没有固定合同的员工，单位突然裁员不再给岗位的情况比比皆是。
算法题：排列序列
嗨，大家好！今天咱们聊个稍微有点“折磨人”的话题——排列序列。
话说，程序员这一行，脑袋经常被各种算法题填满。你要是不碰点数据结构和算法，真的是不好意思说自己是“程序员”啊。今天的主角是排列序列问题。别看这个问题名字很简单，搞不好就能让你从晚上码到天亮，做得你好像已经解锁了整个世界，但回头一看，你又好像啥也没做。
排列序列的基本问题
给你一个整数数组，要求你输出它的所有排列。假设你已经明白了“排列”这个概念，简单来说，它就是把数组里的元素重新排一下顺序，排成一条“新的”序列。
你会发现，问题的难度就在于：对于给定的数字集合，你得想到如何穷举所有可能的排列，而这些排列不允许重复。别小看这个“不允许重复”，你很可能被这个坑给坑得不轻——毕竟如果没有“去重”这一步，整个问题的解法就暴增了。
比如，给定数组 [1, 1, 2]，正确的输出是：
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
如果不去重，你会发现重复的 [1, 1, 2] 和 [1, 2, 1] 等情况会多出来，浪费不必要的时间和空间。
思路和算法
首先，我们可以使用回溯（backtracking）算法来生成所有排列。回溯本质上是通过深度优先搜索（DFS）来构建解决方案，在每一步中尝试不同的选择，然后回溯到上一步去试其他可能的路径。
代码实现的关键点在于：你需要一个used数组来标记某个元素是否已经被使用过，这样就能避免重复的排列出现。
代码实现
import java.util.*;
public class Permutations {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 排序确保相同的元素排列在一起
backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
// 终止条件：当tempList的大小等于nums的长度时，表示一个排列已经完成
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
return;
}
for (int i = 0; i < nums.length; i++) {
// 如果当前元素已经使用过，或者和前一个元素相同并且前一个元素还没被使用过，则跳过
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true; // 标记当前元素已使用
tempList.add(nums[i]);
backtrack(result, tempList, nums, used);
tempList.remove(tempList.size() - 1); // 回溯，移除最后一个元素
used[i] = false; // 重置当前元素的使用状态
}
}
public static void main(String[] args) {
Permutations perm = new Permutations();
int[] nums = {1, 1, 2};
List<List<Integer>> result = perm.permuteUnique(nums);
System.out.println(result);
}
}
代码解析
排序：为了避免重复的排列，我们首先对输入数组进行排序。这样就能确保相同的元素会被相邻排列，方便后续的去重处理。
回溯：我们用一个
tempList来存储当前的排列结果，当tempList的大小和原数组相等时，表示找到了一个有效的排列，就可以把它加入到result中。去重：在循环中，我们会判断当前元素
nums[i]是否已经被使用过，或者和前一个元素相同并且前一个元素还没有被使用过，这样就避免了重复的排列。
复杂度分析
时间复杂度：假设数组
nums的长度是n，则生成所有排列的时间复杂度为O(n!)，因为排列的总数是n!。每次递归过程中，我们都需要处理一个数组的元素，因此时间复杂度与排列数成正比。空间复杂度：空间复杂度主要来自于递归调用栈和存储结果的
result列表。递归的最大深度为n，因此空间复杂度为O(n)，而存储所有排列的空间复杂度为O(n!)。
总结一下
排列序列看起来简单，其实背后有很多要注意的小细节。尤其是当你需要处理重复元素时，去重就显得特别重要。通过回溯算法，你可以穷举所有排列并保证每个排列唯一。
至于我个人来说，做这种排列题目最怕的就是那种细节上的坑——你以为自己已经搞定了所有的情况，结果却忘了去重，最后才发现自己做的所有排列都没意义。🤦♂️ 所以，大家在写这类算法时，记得细心一点，代码中的每一个小细节都很关键！
今天的分享就到这里，如果你有更好的解法或者想法，随时欢迎和我分享哦！
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
