草庐IT

leetcode 47. Permutations II 全排列 II(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 搜索

https://leetcode.cn/problems/permutations-ii

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

二、解题思路

用回溯法解决全排列问题，给定的数组中元素有重复，因此用回溯法执行后的全排列结果中会有重复的，如下图所示。

解决方法，先构造一个hashmap，key是元素，value是元素的个数，然后再用回溯法来解决

三、解题方法

3.1 Java实现

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        // 构造一个hashmap
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int n : nums) {
            int count = countMap.getOrDefault(n, 0);
            countMap.put(n, count + 1);
        }
        dfs(countMap, nums.length, new LinkedList<>(), ans);
        return ans;
    }

    void dfs(Map<Integer, Integer> countMap, int total, Deque<Integer> perm, List<List<Integer>> ans) {
        // 使用双端队列
        if (perm.size() == total) {
            ans.add(new ArrayList<>(perm));
        }
        for (Map.Entry<Integer, Integer> tmp : countMap.entrySet()) {
            if (tmp.getValue() > 0) {
                int oldValue = tmp.getValue();
                perm.offerFirst(tmp.getKey());
                tmp.setValue(tmp.getValue() - 1);
                dfs(countMap, total, perm, ans);
                tmp.setValue(oldValue);
                perm.pollFirst();
            }
        }
    }
}

四、总结小记

  • 2022/6/12 来记录结果的类型要用双端队列
PermutationsleetcodeIntegercountMaplt算法与数据结构

有关leetcode 47. Permutations II 全排列 II(中等)的更多相关文章

  1. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  2. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  3. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  4. ruby - 如何在 ruby 中组合/排列？ - 2

    我有一个熟悉的问题，看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标？badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

  5. ruby - 重复排列 - 2

    我知道如何创建值数组的排列。例如:[*1..3].permutation(2)这导致以下六种排列:[1,2][1,3][2,1][2,3][3,1][3,2]但这个结果缺少三个排列，它们是相同值的组合，即:[1,1][2,2][3,3]如何获得所有排列，包括上面重复的排列？ 最佳答案 尝试#repeated_permutation:[*1..3].repeated_permutation(3).to_a>pp[*1..3].repeated_permutation(3).to_a[[1,1,1],[1,1,2],[1,1,3],[1

  6. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  7. ruby - 按组大小排列的 Active Record 顺序 - 2

    我有一个正在使用group_by的事件记录查询@foo=Foo.group_by(&:relation)然后在我正在使用的View中@foo.eachdo|group,values|groupxhasvalues.countelementsend有没有一种方法可以根据每组的数量对这些进行排序？ 最佳答案 group_by不是ActiveRecord方法，group是。group_by是一个枚举器方法。怎么样@foo=Foo.group('relation').order('count_idasc').count('id')取自"Or

  8. arrays - ruby 中的最佳排列计数算法 - 2

    我正在尝试计算由二进制形式的1和0的P数表示的数字的数量。如果P=2，则表示的数字为0011、1100、0110、0101、1001、1010，所以计数为6。我试过:[0,0,1,1].permutation.to_a.uniq但这不是大数的最佳解决方案(P可以什么可能是最好的排列技术，或者我们是否有任何直接的数学来做到这一点？ 最佳答案 Numberofpermutationcanbecalculatedusingfactorial.a=[0,0,1,1](1..a.size).inject(:*)#=>4!=>24要计算重复项，

  9. ruby - 大写排列 - 2

    我想编写一个ruby​​代码片段，它接受一个字符串并输出所有可能的大写排列。基本上，我有一个我记得的密码，但我不记得它是如何大写的。到目前为止，我有以下内容:defpermute(str)perms=Array.new(2**str.size).times{perms这工作得很好，但我想知道是否有任何ruby​​ists可以帮助我改进它，这样它就不必在带有数字的字符串上不必要地工作。例如，字符串“tst1”生成:tst1tst1tsT1tsT1tSt1tSt1tST1tST1Tst1Tst1TsT1TsT1TSt1TSt1TST1TST1我正在寻找的输出是:tst1tsT1tSt1tS

  10. ruby - 使用 Ruby 和递归查找所有可能的排列 - 2

    我一直在尝试解决一个简单的测验问题，以使用Ruby和递归找到字符串的所有可能排列。我有以下Ruby代码:defpermutation(string)return[string]ifstring.size每当我尝试使用putspermutation("abc")测试代码时，我都会得到以下输出:cacbccbabccbcaccbcacacbcbabcba从理论上讲，这应该是一个非常简单明了的问题，但我确定我做错了什么。很可能它与循环的范围有关。我知道RubyArray类有实例方法permutation来做到这一点，但我正在尝试解决它以进行练习。请注意，当前实现的复杂度为O(N!)。无论如何

随机推荐