JavaScript|LeetCode|搜索|47.全排列Ⅱ

最新推荐文章于 2022-02-16 15:51:10 发布

J_learner

最新推荐文章于 2022-02-16 15:51:10 发布

阅读量255

点赞数

分类专栏： LeetCode 文章标签： leetcode javascript 算法

本文链接：https://blog.csdn.net/J_learner/article/details/104728005

版权

LeetCode 专栏收录该内容

43 篇文章

订阅专栏

法1：回溯
想法：

每一次函数调用，向temp中加入一个之前未加入temp的数字（因为nums中存在重复数字，所以需要另外使用一个arrived数字对应标记nums中数字是否已经加入了temp）
全排列不重复，则需要判断当前符合条件的temp是否已经在结果output中
注：可以先看一下：JavaScript|LeetCode|搜索|46.全排列

/** 
* @param {number[]} nums 
* @return {number[][]} 
*/
var permuteUnique = function(nums) {    
    if(nums.length <= 1) {        
        return [nums];    
    }    
    var temp = [], output = [], arrived = [];    
    var i = 0;    
    for(i = 0; i < nums.length; i++) {        
        arrived[arrived.length] = false;    
    }    
    doPermute(nums, temp, output, arrived);    
    return output;
};

function doPermute(nums, temp, output, arrived) {    
    if(temp.length == nums.length) {        
        var tmp = temp.concat([]);        
        var i = 0;        
        for(i = 0; i < output.length; i++) {            
            if(equal(tmp, output[i])) { // 结果中已经有该数组                
                return;            
            }        
        }        
        output.push(tmp);        
        return;    
    }    
    var i = 0;    
    for(i = 0; i < nums.length; i++) {        
        if(!arrived[i]) {            
            temp.push(nums[i]); // 将数字加入数组            
            arrived[i] = true; // 该数字已经访问            
            doPermute(nums, temp, output, arrived); // 对剩余未访问的数字进行排列
            temp.pop();            
            arrived[i] = false;        
        }    
    }
}

// 比较两个数组
function equal(a, b) {    
    if(a.length != b.length) {        
        return false;    
    }    
    var i = 0, flag = true;    
    for(i = 0; i < a.length; i++) {        
        if(a[i] != b[i]) {            
            flag = false;            
            break;        
        }    
    }    
    return flag;
}

法2：法1+剪枝
看了题解

在法1的基础上，提前排除可能重复的排列，不需要等到后面判断是否已经在结果集合中
nums中重复的数字，优先让处于前面位置的数字占据当前排列的某一位置，则：当前排列的当前位置不会让重复的数字反复占据，实现剪枝
事先将nums升序排列，则重复数字只需比较nums[i - 1]和nums[i]

/** 
* @param {number[]} nums 
* @return {number[][]} 
*/
var permuteUnique = function(nums) {    
    if(nums.length <= 1) {        
        return [nums];    
    }    
    var temp = [], output = [], arrived = [];    
    var i = 0;    
    for(i = 0; i < nums.length; i++) {        
        arrived[arrived.length] = false;    
    }    
    nums.sort(function(a,b) {return a - b});    
    doPermute(nums, temp, output, arrived);    
    return output;
};

function doPermute(nums, temp, output, arrived) {    
    if(temp.length == nums.length) {        
        output.push(temp.concat([]));        
        return;    
    }    
    var i = 0;    
    for(i = 0; i < nums.length; i++) {        
        if(arrived[i]) {            
            continue;        
        }        
        if(i - 1 >= 0 && nums[i] == nums[i - 1] && !arrived[i - 1]) {            
            continue;             
            // 相同的数字，优先让处于前面位置的占据这一位置            
            // 则：当前排列的当前位置不会出现重复数字        
        }        
        temp.push(nums[i]);        
        arrived[i] = true;        
        doPermute(nums, temp, output, arrived);        
        temp.pop();        
        arrived[i] = false;    
    }
}