Algorithm

[LeetCode 47] Permutations II [Java]

顿搜

2018-01-13

0 评论

659 阅读

正在检测是否收录...

01/13

1. Description

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

2. Example

[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

3. Code

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode0047 {

    public List> permuteUnique(int[] nums) {

        List> result = new ArrayList>();

        result.add(new ArrayList());

        for (int i = 0; i < nums.length; i++) {

            Set> currentSet = new HashSet>();

            for (List pre : result) {
                for (int j = 0; j < pre.size() + 1; j++) {

                    pre.add(j, nums[i]);

                    List newList = new ArrayList(pre);

                    pre.remove(j);

                    currentSet.add(newList);
                }
            }
            result = new ArrayList>(currentSet);
        }

        return result;
    }

    public static void main(String[] args) {
        LeetCode0047 leetcode = new LeetCode0047();
        List> result = leetcode.permuteUnique(new int[] { 1,-1,1,2,-1,2,2,-1 });
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}

Math

朗读