Leetcode算法Java全解答--46. 全排列

痛定思痛。 2022-04-11 04:30 184阅读 0赞

# Leetcode算法Java全解答–46. 全排列 #

### 文章目录 ###

*  Leetcode算法Java全解答--46. 全排列
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例

输入: [1,2,3]
    输出:
    [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
    ]

## 想法 ##

将原数组，最终结果数组，某次的数组 进行递归

当循环到最后一个的时候，就往最终结果数组 里面 添加 某次的数组

如果没循环到最后一个的时候,继续调用原来的归方法

## 结果 ##

超过26%的测试案例

时间复杂度/空间复杂度： /n

## 总结 ##

// TODO  
执行过程

result: []smallResult: []
    result: []smallResult: [1]
    result: []smallResult: [1, 2]
    result: []smallResult: [1, 2, 3]
    result: [[1, 2, 3]]smallResult: [1, 3]
    result: [[1, 2, 3]]smallResult: [1, 3, 2]
    result: [[1, 2, 3], [1, 3, 2]]smallResult: [2]
    result: [[1, 2, 3], [1, 3, 2]]smallResult: [2, 1]
    result: [[1, 2, 3], [1, 3, 2]]smallResult: [2, 1, 3]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3]]smallResult: [2, 3]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3]]smallResult: [2, 3, 1]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]smallResult: [3]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]smallResult: [3, 1]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]smallResult: [3, 1, 2]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]smallResult: [3, 2]
    result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]smallResult: [3, 2, 1]

## 代码 ##

### 我的答案 ###

/**************************************
         * 题目
         给定一个没有重复数字的序列，返回其所有可能的全排列。
    
         示例:
    
         输入: [1,2,3]
         输出:
         [
         [1,2,3],
         [1,3,2],
         [2,1,3],
         [2,3,1],
         [3,1,2],
         [3,2,1]
         ]
         **************************************/
    
        /*************************************
         想法：
            将原数组，最终结果数组，某次的数组 进行递归
            当循环到最后一个的时候，就往最终结果数组 里面  添加 某次的数组
            如果没循环到最后一个的时候,继续调用原来的归方法
         我的做法
    
         超过26%的测试案例
         时间复杂度/空间复杂度：  /n
    
         代码执行过程：
    
         总结：
         ************************************/
        public List<List<Integer>> permute(int[] nums) {
    
            if (nums.length == 0) {
                return Collections.EMPTY_LIST;
            }
    
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> smallResult = new ArrayList<>();
            repick(nums, result, smallResult);
            return result;
        }
    
        private void repick(int[] nums, List<List<Integer>> result, List<Integer> smallResult) {
            if (smallResult.size() == nums.length) {
                result.add(new ArrayList<Integer>(smallResult));
            } else {
                for (int i = 0; i < nums.length; i++) {
                    if (smallResult.contains(nums[i])) {
                        continue;
                    }
                    smallResult.add(nums[i]);
                    repick(nums, result, smallResult);
                    smallResult.remove(smallResult.size() - 1);
                }
    
            }
        }

### 大佬们的答案 ###

public List<List<Integer>> better(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(nums == null || nums.length == 0) {
                return result;
            }
            List<Integer> list = new ArrayList<Integer>();
            permute(nums, result, 0, list);
            return result;
        }
    
        public void permute(int[] nums, List<List<Integer>> result, int index, List<Integer> list){
            if(index == nums.length){
                List<Integer> array = new ArrayList<Integer>(list);
                result.add(array);
                return;
            }
            for(int i=index;i<nums.length;i++){
                swap(nums, index, i);
                list.add(nums[index]);
                permute(nums, result, index+1, list);
                // 当list里面存的是Integer的时候，删除Integer传递的int参数，是删除相应位置的元素还是删除对应的Integer对象
                list.remove(list.size()-1);
                swap(nums, index, i);
            }
        }
    
        public void swap(int[] nums, int left, int right){
            if(left == right) {
                return;
            }
            nums[left] ^= nums[right];
            nums[right] ^= nums[left];
            nums[left] ^= nums[right];
        }

### 测试用例 ###

@Test
        public void test046() {
            // 创建测试案例
            int[] arr1 = new int[] { 1, 2, 3 };
    
            // 测试案例期望值
            List<List<Integer>> expResult1 = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            list1.add(2);
            list1.add(3);
            List<Integer> list2 = new ArrayList<>();
            list2.add(1);
            list2.add(3);
            list2.add(2);
            List<Integer> list3 = new ArrayList<>();
            list3.add(2);
            list3.add(1);
            list3.add(3);
            List<Integer> list4 = new ArrayList<>();
            list4.add(2);
            list4.add(3);
            list4.add(1);
            List<Integer> list5 = new ArrayList<>();
            list5.add(3);
            list5.add(1);
            list5.add(2);
            List<Integer> list6 = new ArrayList<>();
            list6.add(3);
            list6.add(2);
            list6.add(1);
            expResult1.add(list1);
            expResult1.add(list2);
            expResult1.add(list3);
            expResult1.add(list4);
            expResult1.add(list5);
            expResult1.add(list6);
    
            // 执行方法
            Solution046 solution046 = new Solution046();
            List<List<Integer>> result1 = solution046.permute(arr1);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult1, result1);
    
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan