算法练习18：全排列（leetcode 46, 47）

题目

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

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

解法

采用递归方式，一个数组的排列，可以将其分而治之

• 第一步，遍历原数组，将其先固定选择一个数，作为已排序好的数组
  [1, 2, 3] =>
  [1], [2, 3]
  [2], [1, 3]
  [3], [1, 2]
• 第二步，将排序好的数组进一步，再详情划分，这里以其中一种来说明，其它同理：
  [1], [2, 3] =>
  [1, 2], [3]
  [1, 3], [2]
• 第三步，再进一步划分：
  [1, 2], [3] => [1, 2, 3]
  [1, 3], [2] => [1, 3, 2]
  此时，已划分好的数组已经是全数组了，所以这个以1开头分支结束，其它的同理

实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let res = []
    function permuteNums(arrageArr, leftArr) {
        // 如果已排列好的序列长度正好等于原数组长度，代表已经排序好了，此时将其放入结果列表中
        if(arrageArr.length === nums.length) {
            res.push(arrageArr)
        // 否则，则向下递归处理
        }else {
            // 对剩余数组遍历
            leftArr.forEach((item, index) => {
                // 选取元素作为已固定的子项，并获取下一个剩余全排列数组
                let temp = [].concat(leftArr)
                // 除去已固定的子项，就是新的剩余排序数组
                temp.splice(index, 1)
                // 将已固定的子项放入已排列好的数组中，对剩余数组继续递归处理
                permuteNums(arrageArr.concat(item), temp)
            })
        }
    }
    permuteNums([], nums)
    return res
};

let arr = [1, 2, 3, 4]
let res = permute(arr)
console.log(res)  
// [ [ 1, 2, 3 ],
//   [ 1, 3, 2 ],
//   [ 2, 1, 3 ],
//   [ 2, 3, 1 ],
//   [ 3, 1, 2 ],
//   [ 3, 2, 1 ] ]

• 时间复杂度：O(n*n!)
• 空间复杂度：O(n)

题目：全排列2(47)

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

第1种，求出所有全排序，然后再去重

缺点：时间复杂度没有减少，明明重复的不需要计算，但依然计算了

var permuteUnique = function(nums) {
  let res = []

  function permuteNums(arrageArr, leftArr) {
    if(arrageArr.length === nums.length) {
      // 判断新的排列数组有没有在之前出现过，如果没有，则增加；否则不处理
      if(!JSON.stringify(res).includes(JSON.stringify(arrageArr))) {
        res.push(arrageArr)
      }
    }else {
      leftArr.forEach((item, index) => {
        let temp = [].concat(leftArr)
        temp.splice(index, 1)
        permuteNums(arrageArr.concat(item), temp)
      })
    }
  }
  permuteNums([], nums)
  return res
};

第2种，判断重复条件，重复的不再递归处理

我们可以先对原数组进行排序，然后再看后一个数是不是等于前一个数，如果是的话，那么这段就是重复，不需要处理
因为这个优化的次数，取决于重复的元素个数，所以是不确定的，但就近似值而言，因为优化没有达到数量级的优化，所以复杂度从数量级看还是没有变的，只是减少一些重复操作。

var permuteUnique2 = function(nums) {
  let res = []
  // 先对原数组排序
  nums.sort((a, b) => a - b)
  
  function permuteNums(arrageArr, leftArr) {
    if(arrageArr.length === nums.length) {
      if(!JSON.stringify(res).includes(JSON.stringify(arrageArr))) {
        res.push(arrageArr)
      }
    }else {
      leftArr.forEach((item, index) => {
        // 如果不是下标值不是第一个，且当前值不等于前一值则继续递归，否则就是重复条件
        if(!(index !==0 && leftArr[index] === leftArr[index - 1])) {
          let temp = [].concat(leftArr)
          temp.splice(index, 1)
          permuteNums(arrageArr.concat(item), temp)
        }

      })
    }
  }
  permuteNums([], nums)
  return res
};

let arr1 = [1,1,2]
let res1 = permuteUnique2(arr1)
console.log(res1)