[数据结构与算法]LeetCode第46-47题 全排列1-2

第一反应

我怎么感觉做过类似的题。
和第31题“下一个排列”对比

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。
更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。
如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列
（即，其元素按升序排列）。

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

反复调用这个，其实就能得到每一种排列。不过这样的效率也太低了。
如果用类似于递归的方法，每次都从剩余的数组中拿出一个数字加入头部，然后对剩下的数组再使用这个方法，这样就可以递归找出每一个剩余的排列组合。空间复杂度也要O(n^2)。这个方法类似于广搜

java知识

这是个大坑

 List<String> list2 = 
 	new ArrayList<String>(Arrays.asList("apple", "banana", "orange"));

注意：

• 适用于对象数组（例如String），不使用于基本数据类型的数组（例如Integer）
• 目标数组和获得的list会相互关联，其中一个改变会影响另一个
• 不支持add()、remove()、clear()等方法，因为这个获得的list和可变长度的那个list不是来自同一个包。如果想要对list做修改，还是用循环把数组里的值一个个放进list比较好

整理自 https://blog.csdn.net/kzadmxz/article/details/80394351

提交通过

真的挺麻烦的，有好几个坑
从list中删除元素，传递list作为参数，list的遍历，array到list的转换，一堆坑。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> end = arrayToList(nums);
        List<List<Integer>> ans = new ArrayList<>();
        ans = bfs(ans, new ArrayList<>(), end);
        return ans;
    }
    public List<List<Integer>> bfs(List<List<Integer>> ans , List<Integer> head , List<Integer> end){
        if(end.size() == 1){
            List<Integer> headNew = copyList(head);
            for(int value:end){
                headNew.add(value);
            }
            ans.add(headNew);
            return ans;
        }
        for(int value:end){
            List<Integer> headNew = copyList(head);
            List<Integer> endNew = copyList(end);
            headNew.add(value);
            removeValue(endNew, value);
            ans = bfs(ans, headNew, endNew);
        }
        return ans;
    }
    public List<Integer> arrayToList(int[] nums){
        List<Integer> end = new ArrayList<Integer>();
        for(int i = 0 ; i < nums.length ; i ++){
            end.add(nums[i]);
        }
        return end;
    }
    public List<Integer> copyList(List<Integer> org){
        List<Integer> ans = new ArrayList<>();
        for(int value:org){
            ans.add(value);
        }
        return ans;
    }
    public void removeValue(List<Integer> list, int target){
        for(int i = 0, len = list.size(); i < len; i++){  
            if(list.get(i) == target){  
                list.remove(i);  
                len--;//list长度减少
                i--;//list删除后右侧数据左移，需要再检查当前下标
            }  
        }
    }
}

下一题

就多了一个可重复的条件

第一反应

算了，本来想着用第31题的方法会超时，再一看不对啊，31题的方法的时间复杂度是O(n)，因为连排序都不用，这样直接循环调用就行。
如果在46题基础上改也好改，主要是i++改成找到下一个不同的数字。
不过我还是改31题试试

提交通过

出乎意料的，改前面的第31题的代码的时候，发现我当时用sort方法不只是偷懒和浪费性能，更是掩盖了我实际上完全没有注意到数组后半截特性，导致的一个严重bug（因为被sort掩盖了）
不过现在修复了。下半段的nextPermutation函数拿去做第31题也没啥问题，也是0ms

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(arrayToList(nums));
        while(nextPermutation(nums)){
            ans.add(arrayToList(nums));
        }
        return ans;
    }

    public boolean nextPermutation(int[] nums) {
        if(nums.length == 1){
            return false;
        }
        // 从后往前找第一个不是递增的数
        int i = nums.length-2;
        int max = nums[nums.length-1];
        for( ; i >= 0 ; i --){
            if( nums[i] < max){
                break;
            }else if(nums[i] > max){
                max = nums[i];
            }
        }
        if(i == -1){
            for(int j = 0 ; j < nums.length/2 ; j ++){
                int temp = nums[j];
                nums[j] = nums[nums.length-1 - j];
                nums[nums.length-1 - j] = temp;
            }
            return false;
        }
        //找到大于nums[i]且最接近nums[i]的数
        int minDiff = 1000;
        int minDiffIndex = -1;
            //由于数组的后半部分认为是从左往右递减排列的，找到目标数字并换位之后，应该保持数组是从左往右递减
            //而考虑到有可能连续多个数字相同，为了保证递减，应该将nums[j] - nums[i] < minDiff 改为 <=（或者从右往左查）
            //这里还可以剪枝
        for(int j = i+1 ; j < nums.length ; j ++ ){
            if(nums[j] > nums[i] && nums[j] - nums[i] <= minDiff){
                minDiff = nums[j] - nums[i];
                minDiffIndex = j;
            }
        }
        //交换minDiffIndex和i位置的数字
        int t = nums[minDiffIndex];
        nums[minDiffIndex] = nums[i];
        nums[i] = t;
        // System.out.println("i+1 = " + (i+1) + " ; nums.length-1 = " +( nums.length-1));
        // for(int k = 0 ; k < nums.length ; k ++){
        //     System.out.print(nums[k] + " ");
        // }
        if((nums.length-1) > i+1 ){
            for(int j = i+1 ; j <= (nums.length-1 + (i+1))/2 ; j ++){
                int temp = nums[j];
                nums[j] = nums[nums.length-1 - (j - (i+1))];
                nums[nums.length-1 - (j - (i+1))] = temp;
            }
        }
        return true;
    }
    public List<Integer> arrayToList(int[] nums){
        List<Integer> end = new ArrayList<Integer>();
        for(int i = 0 ; i < nums.length ; i ++){
            end.add(nums[i]);
        }
        return end;
    }
}