LC-46:全排列(不包含重复元素)


LC-46:全排列

                        
                        

我的实现思路:
该算法是一个对给定序列进行全排列的算法,所以需要对该序列进行递归查询所有的可能出现的序列,比如:[1,2,3] 可能就会出现[1,2,3] , [1,3,2] , [2,1,3] , [2,3,1] , [3,1,2] , [3,2,1],具体是这样分析的,如下图:
                        

在图中会发现一个问题,对于每一个元素的每一种情况都包含在内,但是里面肯定是有重复的序列的,这个时候,完全可以使用Set集合对立面出现的所有的序列进行去重,最终保存剩余的序列,但是为了考虑时间复杂度和空间复杂度的问题,所以这种情况不做考虑。
如何改进呢?
使用回溯法:所谓额回溯法,就是他会对你所有的情况进行遍历,当没有或者说没有符合情况的条件的时候,就会进行回退,实现部分还原,以便对其他的分值进行遍历,在这里我使用的是最经典的visited标志实现对每一个元素的判断。用visited对里面出现的元素设置为true,还没有出现的设置为false,回退时,将已出现的元素标志设置为false。
算法的思路步骤:
第一步:创建一个ArrayList的数组,泛型是一个List<Integer>用于在ArrayList数组中再次存多个数组;
第二步:创建一个visited标志,对原始的数组里面的原有的元素,都保存hashmap中,默认都设置为false;
第三步:声明一个函数,将原始数组、visited、ArrayList最终的结果保存集、再创建一个新的ArrayList用于保存每一个新的完全的序列;
第四步:对该函数进行具体实现,该函数是一个递归函数,首先,实现递归的结束体,只有当新的序列的长度等于数组的长度的时候,就说明,将所有的元素的情况进行遍历完毕,然后将该序列保存在最终的结果集中;接下来就是判断,数组中的每一个元素,for循环,if判断该元素是否没有被遍历过,若没有遍历过,就执行向list序列添加,状态改为true,然后再次执行递归函数,进行深度递归,当递归完成时,是需要进行回溯的,所以进行状态的重新改变,list长度减一。

我的实现代码:
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        HashMap<Integer,Boolean> visited = new HashMap<>();
        for (int number : nums) {
            visited.put(number,false);
        }
        backtracking(nums,result,visited,new ArrayList<Integer>());
        return result;
    }
    public void backtracking(int[] nums,List<List<Integer>> result,HashMap<Integer,Boolean> visited,ArrayList<Integer> list) {
        if (nums.length == list.size()) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            if (!visited.get(temp)) {
                list.add(temp);
                visited.put(temp,true);
                backtracking(nums,result,visited,list);
                list.remove(list.size() - 1);
                visited.put(temp,false);
            }
        }
    }
}

全部评论

相关推荐

爱看电影的杨桃allin春招:我感觉你在炫耀
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务