遞歸算法
以數(shù)組[1, 2, 3, 4]為例输虱，返回全排列
分析：
問(wèn)題可以拆分為
- 1 - 2,3,4 （表示提前元素1和剩余元素2，3，4的全排列）
- 2 - 1,3,4
- 3 - 1,2,4
- 4 - 1,2,3
以上四種情況的并集
var permutation = function (nums) {
let result = []
function swap(i, j) {
let t = nums[i]
nums[i] = nums[j]
nums[j] = t
}
function recall(from, to) {
if (from === to) {
result.push([...nums])
return
}
for (let i = from; i <= to; i++) { // 遍歷所有元素
swap(from, i) // 讓數(shù)組中不同元素提前
recall(from + 1, to) // 剩下元素做全排列
swap(from, i) // 恢復(fù)成原來(lái)的數(shù)組
}
}
recall(0, nums.length - 1)
return result
}
拓展
如果數(shù)組中元素有重復(fù)的情況，如何處理洲劣？
以[1，2课蔬，2囱稽，3]為例
問(wèn)題拆分
- 1 - 2,2,3 （表示1和2，3二跋，4的全排列）
- 2 - 1,2,3
- 3 - 1,2,2
對(duì)于下標(biāo)為1战惊，2的兩個(gè)元素值都為2，所以只需要進(jìn)行一次求解2和1扎即，2吞获，3全排列的操作
var permutation = function (nums) {
let result = []
function swap(i, j) {
let t = nums[i]
nums[i] = nums[j]
nums[j] = t
}
function recall(from, to) {
if (from === to) {
result.push([...nums])
return
}
let swapped = new Set() // 提前元素集合
for (let i = from; i <= to; i++) { // 遍歷所有元素
if (swapped.has(nums[i])){ // 判斷當(dāng)前元素是否已經(jīng)存在被提前的情況
continue
}
swapped.add(nums[i]) // 加入提前元素集合
swap(from, i) // 讓數(shù)組中不同元素提前
recall(from + 1, to) // 剩下元素做全排列
swap(from, i) // 恢復(fù)成原來(lái)的數(shù)組
}
}
recall(0, nums.length - 1)
return result
}
非遞歸算法
以 A[1，2谚鄙，3各拷，4，5]為例
思考
依次從小到大輸出闷营，即為所有全排列
步驟
- 求出最小數(shù)列(所有元素順序?yàn)檫f增的)
- 遞增烤黍，求當(dāng)前數(shù)列的下一個(gè)數(shù)列
- 直到最大數(shù)列(所有元素順序?yàn)檫f減的)結(jié)束
問(wèn)題：如何得到比當(dāng)前數(shù)列大的下一個(gè)數(shù)列呢？
- 從后往前找傻盟，直到A[j - 1] < A[j]
- 找到[j, A.length-1] 中 最小的元素Min[j, A.length-1] 速蕊，交換A[j-1]和Min[j, A.length-1]
- 將[j, A.length - 1]反轉(zhuǎn)
通過(guò)以上三步即可得到比當(dāng)前數(shù)列大的下一個(gè)數(shù)列
/**
* 全排列
* 非遞歸算法
*/
var permutation = function (nums) {
let result = []
function swap(i, j) {
let tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
}
function reverse(start, end) {
if (start >= end) {
return
}
swap(start, end)
reverse(++start, --end)
}
function minIndex(start, end) {
if (start >= end) {
return start
}
let min = Number.MAX_SAFE_INTEGER, minIndex = start
for (let i = start; i <= end; i++) {
if (nums[i] > nums[start - 1]) {
min = Math.min(nums[i], min)
minIndex = i
}
}
return minIndex
}
function next(nums) { // 遞增，求當(dāng)前數(shù)列的下一個(gè)數(shù)列
hasNext = false
for (let j = nums.length - 1; j >= 1; j--) {
if (nums[j - 1] >= nums[j]) { // 元素遞減,繼續(xù)向隊(duì)列頭部遍歷
continue
}
hasNext = true
let pos = minIndex(j, nums.length - 1) // 求[j, length-1]中大于nums[j-1]的最小值下標(biāo)
swap(pos, j - 1) // 交換j-1和Min[j, length-1]
reverse(j, nums.length - 1) // 反轉(zhuǎn) [j, length-1]
break
}
return nums
}
nums = nums.sort(function (a, b) {
return a - b
})
let hasNext = true
while (hasNext) {
result.push([...nums])
nums = next(nums)
}
return result
}
思考：如果有重復(fù)元素怎么辦娘赴？
解答：因?yàn)槭前催f增順序進(jìn)行排列的规哲，重復(fù)也不會(huì)有影響。
