LintCode 子集题目代码

题目

给出一个具有重复数字的列表,找出列表所有不同的排列。

样例 给出列表 [1,2,2],不同的排列有:

Paste_Image.png

代码

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        
        ArrayList<List<Integer>> res = new ArrayList<>();
        
        if(nums == null)
            return null;
        
        if(nums.length == 0)
        {   
            res.add(new ArrayList<Integer>());
            return res;
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        
        //先将数组排序,这样相同元素将会出现在一起
        Arrays.sort(nums);
        
        int n = nums.length;
        int[] visited = new int[n];
        for(int i=0;i<n;i++)
            visited[i] = 0;//0标识未访问
        
        helper(res, list, visited, nums);
        return res;
    }

    private void helper(ArrayList<List<Integer>> res, ArrayList<Integer> list, int[] visited, int[] nums) {
        
        if(nums.length == list.size()) {
            res.add( new ArrayList<Integer>(list));
        }
        
        for(int i=0;i<nums.length;i++) {
            
            if(visited[i] == 1 || i!= 0 && (visited[i-1] == 0 && nums[i] == nums[i-1]))
                continue;
            /*
            上面的判断主要是为了去除重复元素影响。
            比如,给出一个排好序的数组,[1,2,2],那么第一个2和第二2如果在结果中互换位置,
            我们也认为是同一种方案,所以我们强制要求相同的数字,原来排在前面的,在结果
            当中也应该排在前面,这样就保证了唯一性。所以当前面的2还没有使用的时候,就
            不应该让后面的2使用。
            */
            list.add(nums[i]);
            visited[i] = 1;
            helper(res, list, visited, nums);
            list.remove(list.size()-1);
            visited[i] = 0;
            
        }
            
        
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习实践二三事

leetcode之-题19

题目 [图片] Given a linked list, remove the nth node from the end of list and re...

20570
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

28310
来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19590
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

9510
来自专栏从流域到海域

《数据结构》 循环链表和双向链表常用操作代码集合

Ps:每段代码中,添加了署名Solo的代码为博主本人所写,其余来自课本或者老师。 大量操作等同于单链表。重复的操作不再贴出,可以查看之前的博文。 循环链表 //...

20370
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

11030
来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

29930
来自专栏TechBox

数据结构与算法之线性表前言线性表

19950
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

10510
来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

31550

扫码关注云+社区

领取腾讯云代金券