1. 题目要求：
对于给定的可能有重复元素的数组，打印出所有数组中所有元素重新排列的所有可能的不同组合，不要求各个组合之间的顺序
例如:
给出数组[1, 2]
打印结果：
1 2
2 1
2. 解题思路：
- 取出数组中的第一个元素
- 递归调用函数，将剩余元素进行重排，返回值类型为嵌套的数组
- 将取出的元素插入到重排结果中的每一个数组中的每一个位置，依次生成本次递归返回的最终的元素组合之一
- 利用哈希算法去重后，将不重复的元素组合添加到最终要返回的数组中
- 关于去重的算法，可以利用Set中元素查找过程利用了哈希算法的特性，直接根据组合中的所有元素生成一个唯一不会重复的Key，放入Set中即可
进一步探讨：
- 若组合情况太多，可将上面的Key分成两部分，构成[Key1 : [key2]]双散列(key2所在容器为Set)，以避免单个散列表过大，查找耗费时间过长的问题
- 若给定数组中的元素并非简单的Int类型，可将元素依据位置转换成Int数组(新数组中的元素代表原数组中的对象的位置)，对于重复元素，Int值取该元素第一次出现的位置。 将得到的Int数组放入递归函数进行重排，递归函数返回的排列组合为原数组中元素的位置索引，根据位置索引提取原数组中的元素进行打印即可
3. Swift代码
- 递归重排函数
func arrangeArray(array: [Int]) -> [[Int]]{
//元素个数为0时返回空数组
if array.count == 0 {
return [[Int]]()
}
//初始化
var finalArray: [[Int]] = [[Int]]()
var hasRepeatNumber = false //是否需要去重
for i in 0 ..< array.count {
for j in i+1 ..< array.count {
if array[i] == array[j] {
hasRepeatNumber = true
break
}
}
if hasRepeatNumber {
break
}
}
// var hashTable = [String : Set<String>]() //利用字典和Set实现双散列查找
var hashSet = Set<String>() //利用Set实现单散列查找
//排列组合
var tempArray = array
let oneElement = tempArray.removeFirst() //取出一个元素
let returnedArray = arrangeArray(array: tempArray) //剩余元素排列组合
//将取出的元素插入到递归返回的数组中的每一个数组中的每一个位置，并添加到递归函数要返回的数组中
if returnedArray.count == 0 {
finalArray.append([oneElement])
} else {
for oneArray in returnedArray {
for i in 0 ... oneArray.count {
var newArray = oneArray
newArray.insert(oneElement, at: i)
// //双散列去重后添加到finalArray中
// if hasRepeatNumber {
// addNewArrayFilterByDict(hashTable: &hashTable, newArray: &newArray, finalArray: &finalArray)
// } else {
// finalArray.append(newArray)
// }
//单散列去重后添加到finalArray中
if hasRepeatNumber {
addNewArrayFilterBySet(hashSet: &hashSet, newArray: &newArray, finalArray: &finalArray)
} else {
finalArray.append(newArray)
}
}
}
}
return finalArray
}
private func addNewArrayFilterByDict(hashTable: inout [String : Set<String>], newArray: inout [Int], finalArray: inout [[Int]] ) -> Void {
var hashKey1 = String()
var hashKey2 = String()
for j in 0 ..< newArray.count {
if j % 2 == 0 {
if newArray[j] > 9 { //此判断对性能无明显影响
hashKey1 += " " + String(newArray[j]) + " " //两个相邻的非个位数相邻时多添加了一个空格，若增加一个末尾是否是空格的判断，在非个位数占比较少时明显增加运算时间
} else {
hashKey1 += String(newArray[j])
}
} else {
if newArray[j] > 9 {
hashKey2 += " " + String(newArray[j]) + " "
} else {
hashKey2 += String(newArray[j])
}
}
}
if let set = hashTable[hashKey1] {
//已经有内部哈希表进行查找
if set.contains(hashKey2) {
//重复，丢弃
} else {
finalArray.append(newArray)
hashTable[hashKey1]?.insert(hashKey2)
}
} else {
//无内部哈希表时添加内部哈希表，注意字典为值类型
finalArray.append(newArray)
hashTable[hashKey1] = Set<String>()
hashTable[hashKey1]?.insert(hashKey2)
}
}
private func addNewArrayFilterBySet(hashSet: inout Set<String>, newArray: inout [Int], finalArray: inout [[Int]] ) -> Void {
var hashKey = String()
for element in newArray {
if element > 9 { //此判断对性能无明显影响
hashKey += " " + String(element) + " " //两个相邻的非个位数相邻时多添加了一个空格，若增加一个末尾是否是空格的判断，在非个位数占比较少时明显增加运算时间
} else {
hashKey += String(element)
}
}
if hashSet.contains(hashKey) {
//重复，丢弃
} else {
finalArray.append(newArray)
hashSet.insert(hashKey)
}
}
- 调用递归函数并打印结果
let array1 = [1, 2, 1, 2, 10, 2, 3, 2, 3, 10, 1, 1, 2, 1] //双散列查找去重需68s，单散列查找去重需74s
let array2 = [1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 1, 1, 2, 1] //双散列查找去重需21s，单散列查找去重需27s
let array3 = [1, 2, 3, 4, 5, 6, 4, 2, 3, 1, 2]
let array4 = [1, 2, 1, 2]
//print(Date())
let arrangedArray = arrangeArray(array: array4)
//print(Date())
//print(arrangedArray.count)
//遍历数组并打印
for i in 0 ..< arrangedArray.count {
//合成新的字符串
let array = arrangedArray[i]
var string = ""
for j in 0 ..< array.count {
if j == array.count - 1 {
string += String(array[j])
} else {
string += String(array[j]) + " "
}
}
//打印字符串
print(string)
}
- 对于复杂类型数组可将元素的位置数组传入递归函数进行排列，然后再根据返回的位置索引进行打印
let stringArray = ["没", "Bug", "没有", "Bug"]
var indexArray = [Int]()
for i in 0 ..< stringArray.count {
let string = stringArray[i]
let j = stringArray.index(of: string)!
indexArray.append(j)
}
//print(indexArray)
let arrangedIndex = arrangeArray(array: indexArray)
//print(arrangedIndex.count)
for oneArray in arrangedIndex {
var string = ""
for i in 0 ..< oneArray.count {
if i == oneArray.count {
string += stringArray[oneArray[i]]
} else {
string += stringArray[oneArray[i]] + " "
}
}
print(string)
}
欢迎留言讨论。
