LeetcodeアルゴリズムJava全解答--47.全配列II


LeetcodeアルゴリズムJava全解答–47.全配列II
文書ディレクトリ
  • LeetcodeアルゴリズムJava全解答--47.全配列II
  • アイデア
  • 結果
  • まとめ
  • コード
  • 私の答え
  • 大人たちの答え
  • 試験例
  • その他
  • タイトル
    重複する数値を含むことができるシーケンスを指定し、重複しないすべての全配列を返します.
      : [1,1,2]
      :
    [
      [1,1,2],
      [1,2,1],
      [2,1,1]
    ]
      
    

    の意見を打診
    046の方法で、boolean[]visit=new boolean[nums.length];を追加します.すでに入っているデータをtrueに設定
    もう一つの核心はArrays.sort(nums)です.配列のソート
    結果
    43%を超えるテストケース
    時間複雑度/空間複雑度:/
    まとめ
    コード#コード#
    私の答え
       public List> permuteUnique(int[] nums) {
            if (nums.length == 0) {
                return Collections.EMPTY_LIST;
            }
            Arrays.sort(nums);
            boolean[] visit = new boolean[nums.length];
            List> result = new ArrayList<>();
            List smallResult = new ArrayList<>();
            repick(nums, result, smallResult, visit);
            return result;
        }
    
        private void repick(int[] nums, List> result, List smallResult, boolean[] visit) {
            System.out.println("result: " + result.toString() + "smallResult: " + smallResult.toString());
            if (smallResult.size() == nums.length) {
                //            result.add(new ArrayList(smallResult));
                result.add(smallResult);
    
            } else {
                for (int i = 0; i < nums.length; i++) {
                    if (visit[i] || (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
                        continue;
                    }
                    visit[i] = true;
                    List tmp = new ArrayList<>(smallResult);
                    //                smallResult.add(nums[i]);
                    tmp.add(nums[i]);
                    repick(nums, result, tmp, visit);
                    //                smallResult.remove(smallResult.size() - 1);
                    visit[i] = false;
                }
    
            }
        }
    

    みんなの答え
    List> result = new ArrayList<>();
    
        public List> better(int[] nums) {
            if (nums.length == 0) {
                return result;
            }
            Arrays.sort(nums);
            func(new ArrayList(), nums, new boolean[nums.length]);
            return result;
        }
    
        private void func(List candidates, int[] nums, boolean[] used) {
            if (candidates.size() == nums.length) {
                result.add(new ArrayList<>(candidates));
            }
            //    add(candidates)
            else {
                for (int i = 0; i < nums.length; ++i) {
                    if (used[i] || (i != 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                        continue;
                    }
                    used[i] = true;
                    candidates.add(nums[i]);
                    func(candidates, nums, used);
                    used[i] = false;
                    candidates.remove(candidates.size() - 1);
                }
            }
        }
    

    テストケース
        
        @Test
        public void test047() {
            //       
            int[] arr1 = new int[] { 1, 1, 2 };
    
            //        
            List> expResult1 = new ArrayList<>();
            List list1 = new ArrayList<>();
            list1.add(1);
            list1.add(1);
            list1.add(2);
            List list2 = new ArrayList<>();
            list2.add(1);
            list2.add(2);
            list2.add(1);
            List list3 = new ArrayList<>();
            list3.add(2);
            list3.add(1);
            list3.add(1);
            expResult1.add(list1);
            expResult1.add(list2);
            expResult1.add(list3);
    
            //     
            Solution047 solution047 = new Solution047();
            List> result1 = solution047.permuteUnique(arr1);
    
            //          
            Assert.assertEquals(expResult1, result1);
    
        }
    

    その他
    コード管理コードクラウドアドレス:https://gitee.com/lizhaoandroid/LeetCodeAll.git
    他の内容を見るには、コラムや私のブログをクリックしてください.https://blog.csdn.net/cmqwan
    「大物たちの答え」のラベルはleetcodeから来ています.権利侵害は私に連絡して削除してください.
    質問があれば連絡してください、連絡先:QQ 3060507060