`

Leetcode - Permutation II

 
阅读更多
原题链接:https://leetcode.com/problems/permutations-ii/
[分析] 同Permutation一题的区别在于输入数组可能包含重复元素,在面试时即使面试官没有明确指出也该想到。如何处理重复元素不致得到重复结果呢?基本思路是排序然后跳过重复元素。Method1 每次循环递归都要排序且要复制一次数组,时间和空间消耗都比较大,Method2是Code Ganker大神的思路,使用一个额外数组used表示元素是否已经被排好位置。去重的关键是for循环一开始的if判断,理解起来有些费劲,大神的解释:只对第一个未被使用的进行递归,如果第一个重复元素前面的元素还没在当前结果中,那么我们不需要进行递归,这一次结果会出现在第一个的递归函数结果中。举例理解下:假设元素 a 有重复, 下标 i 和 i-1 处均是 a, 处理 i 下标时发现 i-1 下标的 a 还未被使用,这种情况下 i 应当跳过,因为循环是从前往后的推进的,i-1 已先被循环处理过,在这层递归中假设元素将排在位置 k 处,则若不跳过 i ,i 也被放在位置 k 处,最终将导致结果重复。

[ref] Code Ganker大神博客
http://blog.csdn.net/linhuanmars/article/details/21570835

public class Solution {
    public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return result;
        Arrays.sort(nums);
        recur(nums, new boolean[nums.length], new ArrayList<Integer>(), result);
        return result;
    }
    public void recur(int[] nums, boolean[] used, List<Integer> item, List<List<Integer>> result) {
        if (item.size() == nums.length) {
            result.add(new ArrayList<Integer>(item));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && !used[i - 1] && nums[i] == nums[i - 1])
                continue;
            if (!used[i]) {
                item.add(nums[i]);
                used[i] = true;
                recur(nums, used, item, result);
                used[i] = false;
                item.remove(item.size() - 1);
            }
        }
    }
    
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num == null || num.length == 0)
            return result;
        Arrays.sort(num);
        return permutate(num, 0);
    }
    
    private List<List<Integer>> permutate(int[] num, int beg){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(beg == num.length - 1){
            List<Integer> item = new ArrayList<Integer>();
            item.add(num[beg]);
            result.add(item);
            return result;
        }
        
        int origin = num[beg];
        for(int i = beg; i < num.length; i++){
            if(i != beg  && num[i] == num[i - 1])
                continue;
            num[beg] = num[i];
            num[i] = origin;
            
            int[] sub = Arrays.copyOf(num, num.length);
            Arrays.sort(sub, beg + 1, num.length);
            
            for(List<Integer> item : permutate(sub, beg + 1)){
                item.add(0, num[beg]);
                result.add(item);
            }
            num[i] = num[beg];
            num[beg] = origin;
        }
        return result;
    }
}
分享到:
评论

相关推荐

    leetcode-cpp刷题

    ### LeetCode-CPP刷题知识点概述 #### 一、引言 《LeetCode-CPP刷题》是一本针对程序员面试及算法训练的书籍,由戴方勤编著,旨在帮助读者提升解决算法问题的能力,特别是在准备北美乃至全球范围内技术公司的面试时...

    c语言-leetcode题解之0567-permutation-in-string

    c语言入门 c语言_leetcode题解之0567_permutation_in_string

    數位之和leetcode-leetcode-cpp:我的LeetCodeC++答案

    permutation - combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only...

    leetcode-常见考题2.pdf

    - 在 NextPermutation 题目中,需要使用递归或迭代来寻找给定数列的下一个全排列。 这些知识点构成了算法面试的主要考察内容,应聘者如果能熟练掌握这些知识,将有助于在IT行业的面试中获得更好的表现。

    js-leetcode题解之31-next-permutation.js

    1. LeetCode 31题解析:LeetCode是全球知名的技术面试准备平台,题目编号31要求解决的是“下一个排列”的算法问题。这个问题属于算法和编程面试中常见的数组操作类型题目。 2. JavaScript 实现:文章主要以...

    js-leetcode题解之60-permutation-sequence.js

    在解决LeetCode第60题“Permutation Sequence”时,我们面临的问题是找出序列的所有排列中第k小的序列。给定一个由不同数字组成的集合,从中生成所有可能的排列,然后找出所有排列中第k个排列。例如,对于集合[1, 2,...

    leetcode-回文数,回文串(非dp,排序问题哈,dp太难,以后再总结)

    266:https://leetcode-cn.com/problems/palindrome-permutation/ 题目: 思路:判断能否形成回文串,那只要数奇数个字符的种类是否大于2,大于2肯定不可以形成 代码: 409:...

    java-leetcode题解之Palindrome Permutation II.java

    而“Palindrome Permutation II”是众多编程题目中的一道,它主要考察了程序员对字符串处理和排列组合的理解。在这道题目中,通常要求编写一个函数,该函数接受一个字符串作为输入,并返回该字符串所有可能的回文...

    leetcode答案-leetcode-[removed]用javascript刷LeetCode

    另一类常见问题是字符串处理,如"Palindrome Permutation"(回文排列)。我们可以利用JavaScript的字符串方法(如split、reverse、join)和计数器来判断一个字符串是否可以通过重新排列字符形成回文串。 此外,对于...

    java-leetcode题解之Permutation Sequence.java

    java java_leetcode题解之Permutation Sequence.java

    戳气球leetcode-leetcode:leetcode

    leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...

    最低加油次数leetcode-Leetcode:力码

    leetcode TOP 题目 说明 flag TOP hash_map STL TOP 链表操作 链表 TOP 标记每次的begin,一旦发现重复,则需要从这个字母上一次出现的地方的下一个字符为begin 数组 TOP 两指针o(n)遍历变形二分查找,第一个数组找...

    雨水leetcode-Competitive-Coding:包含来自hackerrank、codechef、leetcode、intervie

    1)Permutation_Palindrome - Easy - Codechef - {涵盖了地图(stl)和回文逻辑的最佳使用} 2)句子中单词的出现 - 简单 - Coding Ninjas - {Learned to use 'getline','stringstream','map','itreating over a map'...

    C语言-leetcode题解之47-permutations-ii.c

    标题中的“leetcode题解之47-permutations-ii.c”指的是一段用C语言编写的代码,该代码旨在解决leetcode网站上的算法问题——“47.全排列II”(Permutations II)。这是一个经典的算法题,要求编写一个程序来找出...

    java-leetcode题解之Permutation in String.java

    在Java中解决LeetCode题目的过程中,面对“字符串中的排列”(Permutation in String)这一问题,我们需要编写一段代码来判断一个字符串中是否存在某个排列对应另一个字符串。排列指的是字符串中字符重新排列后形成...

    leetcode567-PermutationInString-Leetcode-567:一种使用字符数组来查找给定字符串的排列是否存在于另一

    在LeetCode的第567题“Permutation In String”中,我们被要求检查一个字符串`str1`是否包含另一个字符串`str2`的排列。换句话说,我们要确定`str2`的所有字符是否可以在`str1`中找到,并且每个字符出现的次数与`str...

    lrucacheleetcode-leetcode-journal:记录所有LeetCode挑战的存储库

    lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划阶段,在这个阶段我将用我自己的话来...Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr

    java-leetcode题解之Next Permutation.java

    2. LeetCode: LeetCode是一个提供算法训练和面试准备的在线平台,包含大量的编程题。通过解决这些题目,可以帮助开发者提升编程技能以及准备技术面试。 3. 题解: 题解是对编程题目的解答和解释。本文提供了Next ...

    LeetCode Permutation

    Source file for LeetCode Permutations Problem

    java-leetcode题解之Letter Case Permutation.java

    Java-leetCode题解之Letter Case Permutation.java的知识点详解: 1. 题目理解: 在leetCode中,Letter Case Permutation是关于字符串转换的一个算法问题。给定一个字符串s,你可以对它进行以下操作任意次数,以...

Global site tag (gtag.js) - Google Analytics