java数据结构与算法刷题-----LeetCode47. 全排列 II

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

此题为46题的衍生题，在46题的基础上，加上了是否重复的判断，除此之外完全一样。

🏆LeetCode46. 全排列https://blog.csdn.net/grd_java/article/details/136683863

1. 暴力回溯

解题思路：时间复杂度O($n^n$),但是严格来说只到了O($n\ast n!$)。空间复杂度O(n)

1. 在46题的基础上增加一些判断是否重复的操作
2. 首先我们先将数组排序，这样我们就能通过两个相邻值的比较，确定当前值是否是一个重复的值（不止一个它）
3. 我们进行全排列时，每个位置可以选择任何不同的值，但是现在有重复的值，就必须确保同一个位置，重复的值只选一次
4. 所以进行全排列时，通过比较相邻的值就可以判断了。但是必须是有序数组才行（重复数字会都挨在一起）

代码

int[] nums;boolean[] numsFlag;//flag数组，true表示当前这个值已经选过int len;List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);this.nums = nums;this.len = nums.length;this.numsFlag = new boolean[len];ArrayList<Integer> records = new ArrayList<>();backTracking(records);return ans;}//回溯算法public void backTracking(List<Integer> records){if(records.size() == len) ans.add(new ArrayList<>(records));//全排列完成后，保存答案else{for(int i = 0;i<len;i++){//每个位置都可以选任何值，但是如果当前数字已被选过，则必须跳过这个值//如果当前值已被选，跳过！ 或者 当前值和上一个一样 并且 上一个也没有被选（说明上一个就已经不能选，选了会重复了）if(this.numsFlag[i]==true || (i>0 && nums[i] == nums[i-1] && this.numsFlag[i-1] == false) ) continue;this.numsFlag[i] = true;//标志为被选过records.add(nums[i]);//选择这个数字backTracking(records);//进行下一个数字的枚举this.numsFlag[i] = false;//枚举完成后，放弃这个值records.remove(records.size()-1);//尝试当前位置下一个可能的值}}}

2. 分区法+回溯

解题思路：时间复杂度O($n\ast n!\ast lo{g}_{2}n$),其中$lo{g}_{2}n$是判断是否重复的时间开销。空间复杂度O(n)

1. 含有重复的元素序列，进行全排列，这个方法就不太好用，因为处理重复很麻烦
2. 所以这里只能通过笨办法，每次选择数字判断是否重复时，从当前位置可选值中，依次遍历判断我们当前要选的数字是否之前就存在过
3. 这个算法依然不需要flag数组标志数字是否已经选择过，也不需要事先排序。
4. 与46题代码几乎完全照搬，只单纯加了一个循环遍历数组，判断是否重复的方法而已。

代码

class Solution {int[] nums;int len;List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] nums) {this.nums = nums;this.len = nums.length;dfs(0);return ans;}private void dfs(int idx) {if (idx == len) {List<Integer> result = new ArrayList<>();for (int num: nums) result.add(num);ans.add(result);}for (int i = idx; i < len; i++) {if (isRepeat(nums, idx, i)) continue;//与46题唯一的不同swap(nums, idx, i);dfs( idx + 1);swap(nums, idx, i);}}//log_2{n},判断当前位置i的取值，是否是重复的（之前取过的值）//与46题唯一的不同private boolean isRepeat(int[] nums, int idx, int i) {while (idx < i) if (nums[idx++] == nums[i]) return true;return false;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}