电商主图设计网站,大连科技网站制作,门户类网站费用,阳新县建设局网站java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 暴力回溯2. 分区法回溯 此题为46题的衍生题#xff0c;在46题…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 暴力回溯2. 分区法回溯 此题为46题的衍生题在46题的基础上加上了是否重复的判断除此之外完全一样。 LeetCode46. 全排列https://blog.csdn.net/grd_java/article/details/136683863
1. 暴力回溯
解题思路时间复杂度O( n n n^n nn),但是严格来说只到了O( n ∗ n ! n*n! n∗n!)。空间复杂度O(n) 在46题的基础上增加一些判断是否重复的操作首先我们先将数组排序这样我们就能通过两个相邻值的比较确定当前值是否是一个重复的值不止一个它我们进行全排列时每个位置可以选择任何不同的值但是现在有重复的值就必须确保同一个位置重复的值只选一次所以进行全排列时通过比较相邻的值就可以判断了。但是必须是有序数组才行重复数字会都挨在一起 代码 int[] nums;boolean[] numsFlag;//flag数组true表示当前这个值已经选过int len;ListListInteger ans new ArrayListListInteger();public ListListInteger permuteUnique(int[] nums) {Arrays.sort(nums);this.nums nums;this.len nums.length;this.numsFlag new boolean[len];ArrayListInteger records new ArrayList();backTracking(records);return ans;}//回溯算法public void backTracking(ListInteger records){if(records.size() len) ans.add(new ArrayList(records));//全排列完成后保存答案else{for(int i 0;ilen;i){//每个位置都可以选任何值但是如果当前数字已被选过则必须跳过这个值//如果当前值已被选跳过 或者 当前值和上一个一样 并且 上一个也没有被选说明上一个就已经不能选选了会重复了if(this.numsFlag[i]true || (i0 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 ∗ n ! ∗ l o g 2 n n*n!*log_2{n} n∗n!∗log2n),其中 l o g 2 n log_2{n} log2n是判断是否重复的时间开销。空间复杂度O(n) 含有重复的元素序列进行全排列这个方法就不太好用因为处理重复很麻烦所以这里只能通过笨办法每次选择数字判断是否重复时从当前位置可选值中依次遍历判断我们当前要选的数字是否之前就存在过这个算法依然不需要flag数组标志数字是否已经选择过也不需要事先排序。与46题代码几乎完全照搬只单纯加了一个循环遍历数组判断是否重复的方法而已。 代码 class Solution {int[] nums;int len;ListListInteger ans new ArrayListListInteger();public ListListInteger permuteUnique(int[] nums) {this.nums nums;this.len nums.length;dfs(0);return ans;}private void dfs(int idx) {if (idx len) {ListInteger 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;}
}
