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

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

1. 暴力回溯

解题思路：时间复杂度O($n^n$),但是严格来说只到了O($n\ast n!$) 因为很多元素只进行了一个判断，没有执行其它操作，所以它们不会很耗费时间，如果把判断算上，则是n^n时间复杂度。空间复杂度O(n)

1. 创建一个flag数组，boolean类型。标志当前数字是否被选过。
2. 我们每个位置的数字枚举时，都先检查flag数组，如果当前数字为false，则可选。
3. 直到所有数字枚举完成

代码

class Solution {int[] nums;boolean[] numsFlag;//flag数组，true表示当前这个值已经选过int len;List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> permute(int[] 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]==false){//如果这个值没有被选this.numsFlag[i] = true;//标志为被选过records.add(nums[i]);//选择这个数字backTracking(records);//进行下一个数字的枚举this.numsFlag[i] = false;//枚举完成后，放弃这个值records.remove(records.size()-1);//尝试当前位置下一个可能的值}}}}
}

2. 分区法+回溯

解题思路:时间复杂度O($n\ast n!$),空间复杂度O(n)

1. 将数组分为两个区域，用index下标分割，index左边保存当前已经选择的数字，右边保存剩余可选的数字
2. 每次通过交换操作，将我们想要在这次选择的数字，移动到index位置，然后index++
3. 下个数字只能从index和index后面的位置选取。这样就自动跳过了已经选取过的数字。而不用flag数组进行额外的判断

代码

class Solution {List<List<Integer>> ans = new ArrayList<>();int[] nums;public List<List<Integer>> permute(int[] nums) {this.nums = nums;backTracking( 0);return ans;}/*** 回溯算法* @param index 表示当前可选值的下标* 将数组人为分成两部分[ 已选数字 | 剩余可选数字 ]，就是通过index下标来区分，index左边是已选数字，右边是可选数字* 我们通过交换操作，每次将选中的数字放到左边，那么剩余的可选数字都会在右边* 这样每次选择数字时，已经选过的就直接跳过了，不需要再用一个boolean类型数组来标志哪些数字没有被选过*/public void backTracking(int index){if (index == nums.length) {//全排列，一定是所有元素都参与排列组合List<Integer> list = new ArrayList<>();for( int num : nums ) list.add(num);ans.add(list);}else {//j表示当前位置的可选值，是前面选剩下的元素for (int j = index; j < nums.length; j++) {//j表示当前位置选哪个值，一定是所有可选的都要枚举一遍//选中j元素，则将j元素放入已选区域swap(nums, index, j);//放入一个j元素进入已选区域后，index指针后移，进行下一个位置的选取backTracking(index + 1);//枚举不选择当前j元素的情况，则将j放回原位。然后尝试下一个可选值。swap(nums, j, index);//}}}private void swap(int[] nums, int i, int j){if (i == j) return;nums[i] = nums[i] ^ nums[j];nums[j] = nums[i] ^ nums[j];nums[i] = nums[i] ^ nums[j];}}