在实现LeetCode的问题记录
- 两数之和
未通过方案
在使用一次遍历，然后寻找数组中是否包含 array.contains(tartget - nums[i]), 再获取complement的索引，该索引和i不相等。代码如下:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0 ..< nums.count {
let complement = target - nums[i]
if nums.contains(complement) {
if let index = nums.index(of: complement) {
if index != i {
return [i, index]
}
}
}
}
fatalError("No tow sum solution.")
}
提交代码的时候未能通过第20的testcase，
根据结果提示，是在超大数组的情况下，该算法会超时，说明在使用Swift Array.contains / Array.index方法在性能在大数据下存在问题，为此去查看文档介绍
Computational Complexity The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(Nlg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(Nlg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.
• 在数组中通过一个特定的索引获取值的时间复杂度最坏是`O(log n)`，但通常应该是`O(1)`。
• 搜索一个未知索引的对象的时间复杂度最坏是`O(n (log n))`，但一般应该是`O(n)`。
• 插入或者删除一个对象最坏的时间复杂度是`O(n (log n))`，但经常是`O(1)`
因此需要寻找性能更好的方法是实现，Java中可使用HashMap高效的判断表中是否包含某个obj，并且获取这个obj的key,Swift中的Dictionary并没有提供判断是否存在特定value，并获取该value对应的key。
进一步寻找高性能方案二
由于我的目的是寻找类似于HashTable的高性能检索方案，而Swift的集合类型都是属于Foundation框架，参考文章(小声说：找到了一个高质量的翻译文章)， 发现了NSOrderedSet集合类型，对应的可变类型为NSMutableOrderedSet，是一种允许你以特定顺序存储一组不重复对象的数据结构，其相对于数组的区别在于：
当元素顺序以及测试某个元素是否存在于集合中的性能很重要时，你可使用有序的集合作为数组的备选项
😆😆😆，这不就是我正要需要的吗，立马修改代码，将nums数组作为参数创建一个NSOrderedSet对象，然后使用orderSet去检索complement并获取其索引
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
let orderSet = NSOrderedSet(array: nums)
for i in 0 ..< nums.count {
let complement = target - nums[i]
if orderSet.contains(complement) {
if let index = nums.index(of: complement) {
if index != i {
return [i, index]
}
}
}
}
fatalError("No tow sum solution.")
}
再次提交代码顺利通过测试，得出结果：
方案三
想法： 将输入数组的每个值作为Key，将其Index作为Value，存放在字典中，利用Dictionary的以下特性，可以很大可能获取到O(1)的效果：
1. 从字典中获取值的时间复杂度最坏是O(n)，但一般应该是O(1)。
2. 插入和删除数据的时间复杂度最坏是O(n²)，但由于顶层的优化通常更接近O(1)。
得到代码如下：
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dic = [Int: Int]()
for index in 0 ..< nums.count {
dic[nums[index]] = index
}
for i in 0 ..< nums.count {
let complement = target - nums[i]
if let index = dic[complement], i != index{
return [i, index]
}
}
fatalError("No tow sum solution.")
}
首先遍历nums，将nums[i]作为key，i作为value存放在字典中，然后再进行一次遍历，利用complement从字典中取index，如果存在index && index != i， 那么就的我们需要的结果[i, index]， 通过测试，提交答案，得到通过结果如下：
由结果可以看出这种方式只需要24ms，相对OrderSet方式80ms有了3倍多的提升，说明想法成立。
方案四：NSMapTable
在Swift 4.1中使用一下方式初始化mapTable会出现报错
// 初始化
let mapTable = NSMapTable<AnyObject, AnyObject>.init(keyOptions: .integerPersonality, valueOptions: .integerPersonality)
// 报错
libc++abi.dylib: terminating with uncaught exception of type NSException
但是换成下面的方式就没有问题
// 成功的初始化
let mapTable = NSMapTable<AnyObject, AnyObject>(keyOptions: NSPointerFunctions.Options.weakMemory, valueOptions: NSPointerFunctions.Options.weakMemory)
二者的区别在于 .integerPersonality 和 NSPointerFunctions.Options.weakMemory，需要进一步查看二者的区别， 是integerPersonality与weakMemory的具体语义
LeetCode结果 无法识别NSMapTable类，看来得换个方式了。
Line 5: use of unresolved identifier 'NSMapTable'