0 0 vote
Article Rating
Subscribe
提醒
guest
3 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
暴走的楚狂

简单又快速的解法:

# python 3
class Solution:
    def permuteUnique(self, nums, trace=[]):
        if len(nums) <= 1:
            return [nums + trace]
        result = []
        visited = set()
        for i, num in enumerate(nums):
            if num not in visited:
                result += self.permuteUnique(nums[:i] + nums[i + 1 :], trace + [num])
                visited.add(num)
        return result

gh_BMDACMER

// 方法一 跟昨天一样 只是换个hashset保存 效率低下 java运行64ms 击败9.71%

public List<List<Integer>> permuteUnique(int[] nums) {
    int len = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    if (len == 0) return res;

    Set<List<Integer>> set = new HashSet<>();
    *//**
     * path ---- 路径
     * depth --- 深度   默认为0   也即一个元素都不取
     * Set -- 存放结果集(去重的)
     * used -- 用以标记是否访问该元素
     *//*
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used = new boolean[len];
    int depth = 0;
    dfs(nums, len, depth, path, used, set);

    for (List<Integer> list : set) {
        res.add(list);
    }
    return res;
}

private void dfs(int[] nums, int len, int depth, LinkedList<Integer> path, boolean[] used, Set<List<Integer>> set) {
    if (len == depth) {
        set.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < len; i++) {
        if (used[i]) continue;
        path.addLast(nums[i]);
        used[i] = true;
        dfs(nums, len, depth + 1, path, used, set);
        path.removeLast();
        used[i] = false;
    }
}

// 方法二 先排序 如果相邻元素相同 则忽略(直接遍历下下个) java运行2ms 击败66.18%

public List<List<Integer>> permuteUnique(int[] nums) {
    int len = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    if (len == 0) return res;

    Arrays.sort(nums);  // 为了去重
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used = new boolean[len];
    int depth = 0;
    dfs(nums, len, depth, path, used, res);
    return res;
}

private void dfs(int[] nums, int len, int depth, LinkedList<Integer> path, boolean[] used, List<List<Integer>> res) {
    if (len == depth) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < len; i++) {
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
            continue;
        path.addLast(nums[i]);
        used[i] = true;
        dfs(nums, len, depth + 1, path, used, res);
        path.removeLast();
        used[i] = false;
    }

}
Hao
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.ans = []
        
        def backtrack(cur, total):
            if not total and cur not in self.ans:
                self.ans.append(cur[:])
                return
            
            for i in range(len(total)):
                cur.append(total[i])
                backtrack(cur, total[:i] + total[i+1:])
                cur.pop(-1)
        
        backtrack([], nums)
        return self.ans

对数组进行排序后每次直接选择不同的数字,或者直接套模板后,加一个判断,看当前数组在不在之前的结果中。