力扣00047.全排列 II

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 8 分钟
全排列 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

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, path, result);
        return result;
    }
private:
    void backtrack(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

结果

执行用时 : 4 ms, 击败 90.72% 使用 C++ 的用户

内存消耗 : 10.72 MB, 击败 29.84% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, path, result);
        return result;
    }
    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

结果

执行用时 : 1 ms, 击败 99.84% 使用 Java 的用户

内存消耗 : 43.82 MB, 击败 25.69% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
        path = []
        used = [False] * len(nums)
        self.backtrack(nums, used, path, result)
        return result
    def backtrack(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                continue
            used[i] = True
            path.append(nums[i])
            self.backtrack(nums, used, path, result)
            path.pop()
            used[i] = False

结果

执行用时 : 28 ms, 击败 70.21% 使用 Python 的用户

内存消耗 : 11.70 MB, 击败 98.38% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        path = []
        used = [False] * len(nums)
        self.backtrack(nums, used, path, result)
        return result
    def backtrack(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                continue
            used[i] = True
            path.append(nums[i])
            self.backtrack(nums, used, path, result)
            path.pop()
            used[i] = False

结果

执行用时 : 39 ms, 击败 93.93% 使用 Python3 的用户

内存消耗 : 16.72 MB, 击败 37.36% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void backtrack(int* nums, int numSize, int** ans, int* ansSize, int idx, int* perm, int* used) {
    if (idx == numSize) {
        int* tmp = malloc(sizeof(int) * numSize);
        memcpy(tmp, perm, sizeof(int) * numSize);
        ans[(*ansSize)++] = tmp;
        return;
    }
    for (int i = 0; i < numSize; ++i) {
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
            continue;
        }
        perm[idx] = nums[i];
        used[i] = 1;
        backtrack(nums, numSize, ans, ansSize, idx + 1, perm, used);
        used[i] = 0;
    }
}
int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int** ans = malloc(sizeof(int*) * 2001);
    int* perm = malloc(sizeof(int) * 2001);
    int* used = malloc(sizeof(int) * numsSize);
    memset(used, 0, sizeof(int) * numsSize);
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = 0;
    backtrack(nums, numsSize, ans, returnSize, 0, perm, used);
    *returnColumnSizes = malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    free(used);
    return ans;
}

结果

执行用时 : 20 ms, 击败 95.75% 使用 C 的用户

内存消耗 : 9.37 MB, 击败 93.46% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        IList<int> path = new List<int>();
        bool[] used = new bool[nums.Length];
        Backtrack(nums, used, path, result);
        return result;
    }
    private void Backtrack(int[] nums, bool[] used, IList<int> path, IList<IList<int>> result) {
        if (path.Count == nums.Length) {
            result.Add(new List<int>(path));
            return;
        }
        for (int i = 0; i < nums.Length; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.Add(nums[i]);
            Backtrack(nums, used, path, result);
            path.RemoveAt(path.Count - 1);
            used[i] = false;
        }
    }
}

结果

执行用时 : 101 ms, 击败 89.89% 使用 C# 的用户

内存消耗 : 48.13 MB, 击败 40.45% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const path = [];
    const used = new Array(nums.length).fill(false);
    backtrack(nums, used, path, result);
    return result;
};
function backtrack(nums, used, path, result) {
    if (path.length === nums.length) {
        result.push([...path]);
        return;
    }
    for (let i = 0; i < nums.length; ++i) {
        if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
            continue;
        }
        used[i] = true;
        path.push(nums[i]);
        backtrack(nums, used, path, result);
        path.pop();
        used[i] = false;
    }
}

结果

执行用时 : 75 ms, 击败 67.66% 使用 JavaScript 的用户

内存消耗 : 52.87 MB, 击败 19.25% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const result: number[][] = [];
    const path: number[] = [];
    const used: boolean[] = new Array(nums.length).fill(false);
    backtrack(nums, used, path, result);
    return result;
}
function backtrack(nums: number[], used: boolean[], path: number[], result: number[][]): void {
    if (path.length === nums.length) {
        result.push([...path]);
        return;
    }
    for (let i = 0; i < nums.length; ++i) {
        if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
            continue;
        }
        used[i] = true;
        path.push(nums[i]);
        backtrack(nums, used, path, result);
        path.pop();
        used[i] = false;
    }
}

结果

执行用时 : 70 ms, 击败 93.66% 使用 TypeScript 的用户

内存消耗 : 54.05 MB, 击败 28.87% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {
        sort($nums);
        $result = [];
        $path = [];
        $used = array_fill(0, count($nums), false);
        $this->backtrack($nums, $used, $path, $result);
        return $result;
    }
    private function backtrack($nums, &$used, &$path, &$result) {
        if (count($path) === count($nums)) {
            $result[] = $path;
            return;
        }
        for ($i = 0; $i < count($nums); ++$i) {
            if ($used[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$used[$i - 1])) {
                continue;
            }
            $used[$i] = true;
            $path[] = $nums[$i];
            $this->backtrack($nums, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
}

结果

执行用时 : 7 ms, 击败 94.44% 使用 PHP 的用户

内存消耗 : 20.77 MB, 击败 5.55% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        var nums = nums.sorted()
        var result = [[Int]]()
        var path = [Int]()
        var used = [Bool](repeating: false, count: nums.count)
        backtrack(nums: &nums, used: &used, path: &path, result: &result)
        return result
    }
    private func backtrack(nums: inout [Int], used: inout [Bool], path: inout [Int], result: inout [[Int]]) {
        if path.count == nums.count {
            result.append(Array(path))
            return
        }
        for i in 0..<nums.count {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue
            }
            used[i] = true
            path.append(nums[i])
            backtrack(nums: &nums, used: &used, path: &path, result: &result)
            path.removeLast()
            used[i] = false
        }
    }
}

结果

执行用时 : 16 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 16.30 MB, 击败 5.00% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    fun permuteUnique(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val path = mutableListOf<Int>()
        val used = BooleanArray(nums.size)
        nums.sort()
        backtrack(nums, used, path, result)
        return result
    }
    private fun backtrack(nums: IntArray, used: BooleanArray, path: MutableList<Int>, result: MutableList<List<Int>>) {
        if (path.size == nums.size) {
            result.add(path.toList())
            return
        }
        for (i in nums.indices) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue
            }
            used[i] = true
            path.add(nums[i])
            backtrack(nums, used, path, result)
            path.removeAt(path.size - 1)
            used[i] = false
        }
    }
}

结果

执行用时 : 248 ms, 击败 66.67% 使用 Kotlin 的用户

内存消耗 : 39.59 MB, 击败 66.67% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  List<List<int>> permuteUnique(List<int> nums) {
    nums.sort();
    List<List<int>> result = [];
    List<int> path = [];
    List<bool> used = List.filled(nums.length, false);
    void backtrack() {
      if (path.length == nums.length) {
        result.add([...path]);
        return;
      }
      for (int i = 0; i < nums.length; ++i) {
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
          continue;
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack();
        path.removeLast();
        used[i] = false;
      }
    }
    backtrack();
    return result;
  }
}

结果

执行用时 : 318 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 147.68 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	var result [][]int
	var path []int
	used := make([]bool, len(nums))
	var backtrack func()
	backtrack = func() {
		if len(path) == len(nums) {
			result = append(result, append([]int(nil), path...))
			return
		}
		for i := 0; i < len(nums); i++ {
			if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			backtrack()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	backtrack()
	return result
}

结果

执行用时 : 3 ms, 击败 62.79% 使用 Go 的用户

内存消耗 : 3.52 MB, 击败 96.43% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# @param {Integer[]} nums
# @return {Integer[][]}
def permute_unique(nums)
  nums.sort!
  result = []
  path = []
  used = Array.new(nums.length, false)
  backtrack = lambda do
    if path.length == nums.length
      result.push(path.dup)
      return
    end
    nums.each_with_index do |num, i|
      next if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
      used[i] = true
      path.push(num)
      backtrack.call
      path.pop
      used[i] = false
    end
  end
  backtrack.call
  result
end

结果

执行用时 : 84 ms, 击败 80.00% 使用 Ruby 的用户

内存消耗 : 206.89 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import scala.collection.mutable._

object Solution {
  def dfs(curres: Stack[Int], nums: Array[Int], states: Array[Boolean], res: ArrayBuffer[List[Int]]): Unit = {
    if (curres.length == nums.length) {
      res.append(curres.toList)
      return
    }
    var used = Set[Int]()
    for (i <- 0 until nums.length) {
      if (states(i) && !used(nums(i))) {
        curres.push(nums(i))
        states(i) = false
        dfs(curres, nums, states, res)
        curres.pop()
        states(i) = true
        used += nums(i)
      }
    }
  }
  def permuteUnique(nums: Array[Int]): List[List[Int]] = {
    val states = Array.fill(nums.length)(true)
    val res = ArrayBuffer[List[Int]]()
    val curres = Stack[Int]()
    dfs(curres, nums.sorted, states, res)
    res.toList
  }
}

结果

执行用时 : 544 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 57.75 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
    pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut path = Vec::new();
        let mut used = vec![false; nums.len()];
        fn backtrack(nums: &Vec<i32>, used: &mut Vec<bool>, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
            if path.len() == nums.len() {
                result.push(path.clone());
                return;
            }
            let mut prev_used = None;
            for i in 0..nums.len() {
                if used[i] || Some(nums[i]) == prev_used {
                    continue;
                }
                prev_used = Some(nums[i]);
                path.push(nums[i]);
                used[i] = true;
                backtrack(nums, used, path, result);
                path.pop();
                used[i] = false;
            }
        }
        let mut nums_sorted = nums.clone();
        nums_sorted.sort();
        backtrack(&nums_sorted, &mut used, &mut path, &mut result);
        result
    }
}

结果

执行用时 : 3 ms, 击败 47.37% 使用 Rust 的用户

内存消耗 : 2.14 MB, 击败 55.26% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户