当前位置：首页 > article >正文

前端面试笔试（六）

article 2024/11/28 22:03:23

上一篇是不含重复数字的数组全排列，这篇是有重复数字的数组全排列，要判断得多一点

题目

有重复项数字的全排列（递归回溯，js解法）

解决

代码

详情

变量初始化以及排序

递归函数dg

递归终止条件

递归主体和去重

初始调用和返回结果

题目

有重复项数字的全排列（递归回溯，js解法）

解决

代码

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */
function permuteUnique(num) {
    // write code here
    num = num.sort((a, b) => a - b); //排序
    let len = num.length;
    let res = [];
    let path = []; //临时排列的数组
    let used = []; //使用过的数组

    function dg(num) {
        if (path.length === len) {
            return res.push(path.slice());
        }
        for (let i = 0; i < len; i++) {
            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
                //当前的元素num[i]与同一层的前一个元素num[i-1]相同并且num[i-1]已经用过
                continue;
            }
            if (!used[i]) {
                //元素未被使用
                path.push(num[i]);//元素加到临时数组
                used[i] = true; //标记为使用过
                dg(num);
                path.pop(); //回溯
                used[i] = false; //不同层
            }
        }
    }
    dg(num);
    return res;
}
module.exports = {
    permuteUnique: permuteUnique,
};

详情

这个函数使用了回溯算法来实现这一目标。这个函数接受一个参数num，它是一个可能包含重复数字的数组，包含要生成排列的数字。

变量初始化以及排序

num = num.sort((a, b) => a - b); // 排序
let len = num.length;
let res = [];
let path = []; // 临时排列的数组
let used = []; // 使用过的数组

首先，对输入数组num进行升序排序，这是为了确保生成的排列是按照字典序排列的。
len变量存储数组num的长度。
res数组用于存储所有生成的唯一排列。
path数组用于构建当前的排列。
used数组是一个布尔数组，用于跟踪哪些元素已经被添加到当前的path中。

递归函数`dg`

function dg(num) {
    // ...
}

dg是一个递归函数，用于生成排列。它接受一个参数num，这是当前要处理的数组（实际上是原始数组的一个引用，因为在函数外部已经对它进行了排序）。

递归终止条件

if (path.length === len) {
    return res.push(path.slice());
}

当path的长度等于输入数组num的长度时，意味着一个完整的排列已经生成。此时，将该排列（path的一个副本）添加到结果数组res中。

递归主体和去重

for (let i = 0; i < len; i++) {
    if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
        // 当前的元素num[i]与同一层的前一个元素num[i-1]相同并且num[i-1]没有用过
        // 这意味着如果现在选择num[i]，将会生成一个与之前相同的排列
        // 因此，跳过这个元素，以避免生成重复的排列
        continue;
    }
    if (!used[i]) {
        // 元素未被使用
        path.push(num[i]); // 元素加到临时数组
        used[i] = true; // 标记为使用过
        dg(num); // 递归调用，继续生成排列
        path.pop(); // 回溯，移除刚刚添加的元素
        used[i] = false; // 标记为未使用，以便在后续的迭代中可以再次选择它
    }
}

这个循环遍历数组num的每个元素。

对于每个元素，首先检查它是否与前一个元素相同，并且前一个元素是否没有被使用过。如果是这种情况，那么跳过当前元素，以避免生成重复的排列。

否则，如果元素未被使用（used[i]为false），则将其添加到path中，标记为已使用，递归调用dg函数继续生成排列，然后回溯（移除刚刚添加的元素，并将其标记为未使用）。