当前位置: 面试刷题>> 全排列Ⅱ (经典算法题500道)


题目描述补充

题目:全排列 II

给定一个可能包含重复数字的整数数组 nums,返回该数组所有可能的排列。

注意

  1. 你可以按任意顺序返回答案。
  2. 数组中可能包含重复元素。

示例 1:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

示例 2:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

PHP 代码示例

function permuteUnique($nums) {
    sort($nums); // 先排序,便于后续去重
    $result = [];
    backtrack($nums, [], $result);
    return $result;
}

function backtrack(&$nums, $temp, &$result) {
    if (count($temp) == count($nums)) {
        $result[] = $temp;
        return;
    }
    
    for ($i = 0; $i < count($nums); $i++) {
        // 跳过重复元素
        if ($i > 0 && $nums[$i] == $nums[$i - 1] && !in_array($nums[$i], $temp)) {
            continue;
        }
        
        $temp[] = $nums[$i];
        $newNums = array_diff_assoc($nums, array_slice($nums, 0, $i + 1)); // 排除已使用的元素
        backtrack($newNums, $temp, $result);
        array_pop($temp); // 回溯
    }
}

// 测试
$nums = [1, 1, 2];
$result = permuteUnique($nums);
print_r($result);

Python 代码示例

from itertools import permutations

def permuteUnique(nums):
    nums.sort() # 先排序
    result = []
    seen = set() # 用于去重
    
    def backtrack(first=0):
        if first == n and tuple(nums) not in seen:
            seen.add(tuple(nums))
            result.append(list(nums))
        for i in range(first, n):
            if i > first and nums[i] == nums[i-1]:
                continue
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
    
    n = len(nums)
    backtrack()
    return result

# 测试
nums = [1, 1, 2]
print(permuteUnique(nums))

JavaScript 代码示例

function permuteUnique(nums) {
    nums.sort((a, b) => a - b); // 先排序
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            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;
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];
            used[i] = false;
        }
    }
    
    backtrack(0);
    return result;
}

// 测试
const nums = [1, 1, 2];
console.log(permuteUnique(nums));

以上三个示例分别展示了在 PHP、Python 和 JavaScript 中如何解决全排列 II 的问题,并且都考虑到了数组中可能存在重复元素的情况。码小课网站中有更多相关内容分享给大家学习,可以帮助大家深入理解算法和数据结构。

推荐面试题