上次講解了基本的語法和一些Swift的小技巧诵闭。這期我們來看幾個最基本的數(shù)據(jù)結(jié)構(gòu)：數(shù)組炼团，字符串，集合和字典疏尿。
數(shù)組
數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)瘟芝。Swift中改變了以前Objective-C時代NSMutableArray和NSArray分開的做法，統(tǒng)一到了Array唯一的數(shù)據(jù)結(jié)構(gòu)褥琐。雖然看上去就一種數(shù)據(jù)結(jié)構(gòu)锌俱，其實它的實現(xiàn)有三種：
ContiguousArray<Element>：效率最高，元素分配在連續(xù)的元素上敌呈。如果數(shù)組是值類型（棧上操作）贸宏，Swift會自動調(diào)用Array的這種實現(xiàn)；如果注重效率磕洪，推薦聲明這種類型吭练，尤其是在大量元素是類時，這樣做效果會很好析显。
Array<Element>：會自動橋接到 Objective-C 中的 NSArray线脚，如果是值類型，其性能與ContiguousArray無差別。
ArraySlice<Element>：它不是一個新的數(shù)組浑侥。只是一個片段姊舵，內(nèi)存上與原數(shù)組享用同一區(qū)域。
下面是數(shù)組最基本的一些運用寓落。
// 聲明一個不可修改的數(shù)組
let nums = [1, 2, 3]
let nums = [Int](repeating: 0, count: 5)
// 聲明一個可以修改的數(shù)組
var nums = [3, 1, 2]
// 增加一個元素
nums.append(4)
// 對原數(shù)組進行升序排序
nums.sort()
// 對原數(shù)組進行降序排序
nums.sort(by: >)
// 將原數(shù)組除了最后一個以外的所有元素賦值給另一個數(shù)組
let anotherNums = Array(nums[0 ..< nums.count - 1])
不要小看這些簡單的操作：數(shù)組可以依靠它們實現(xiàn)更多的數(shù)據(jù)結(jié)構(gòu)括丁。Swift雖然不像Java中有現(xiàn)成的隊列和棧，但我們完全可以用數(shù)組配合最簡單的操作實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)伶选，下面就是用數(shù)組實現(xiàn)棧的示例代碼史飞。
// 用數(shù)組實現(xiàn)棧
class Stack {
var stack: [AnyObject]
var isEmpty: Bool { return stack.isEmpty }
var peek: AnyObject? { return stack.last }
init() {
stack = [AnyObject]()
}
func push(object: AnyObject) {
stack.append(object)
}
func pop() -> AnyObject? {
if (!isEmpty()) {
return stack.removeLast()
} else {
return nil
}
}
}
最后特別強調(diào)一個操作：reserveCapacity()。它用于為原數(shù)組預留空間仰税，防止數(shù)組在增加和刪除元素時反復申請內(nèi)存空間或是創(chuàng)建新數(shù)組构资，特別適用于創(chuàng)建和removeAll()時候進行調(diào)用，為整段代碼起到提高性能的作用陨簇。
字典和集合
這兩個數(shù)據(jù)結(jié)構(gòu)經(jīng)常使用的原因在于吐绵，查找數(shù)據(jù)的時間復雜度為O(1)。一般字典和集合要求它們的Key都必須遵守Hashable協(xié)議河绽，Cocoa中的基本數(shù)據(jù)類型都滿足這一點己单；自定義的class需要實現(xiàn)Hashable，而又因為Hashable是對Equable的擴展耙饰，所以還要重載 == 運算符纹笼。
下面是關(guān)于字典和集合的一些實用操作：
let oddNums: Set = [1, 3, 5, 7, 9]
let primeNums: Set = [3, 5, 7, 11, 13]
// 交集、并集苟跪、差集
let oddAndPrimeNums = primeNums.intersection(oddNums)
let oddOrPrimeNums = primeNums.union(oddNums)
let oddNotPrimeNums = oddNums.subtracting(primeNums)
// 用字典和高階函數(shù)計算字符串中每個字符的出現(xiàn)頻率
Dictionary("hello".map { ($0, 1) }, uniquingKeysWith: +)
集合和字典在實戰(zhàn)中經(jīng)常與數(shù)組配合使用廷痘，請看下面這道算法題：
給一個整型數(shù)組和一個目標值，判斷數(shù)組中是否有兩個數(shù)字之和等于目標值
這道題是傳說中經(jīng)典的2Sum件已，我們已經(jīng)有一個數(shù)組記為nums牍疏，也有一個目標值記為target，最后要返回一個Bool值拨齐。
最粗暴的方法就是每次選中一個數(shù)鳞陨，然后遍歷整個數(shù)組，判斷是否有另一個數(shù)使兩者之和為target瞻惋。這種做法時間復雜度為O(n^2)厦滤。
采用集合可以優(yōu)化時間復雜度。在遍歷數(shù)組的過程中歼狼，用集合每次保存當前值掏导。假如集合中已經(jīng)有了目標值減去當前值，則證明在之前的遍歷中一定有一個數(shù)與當前值之和等于目標值羽峰。這種做法時間復雜度為O(n)趟咆，代碼如下添瓷。
func twoSum(nums: [Int], _ target: Int) -> Bool {
var set = Set<Int>()
for num in nums {
if set.contains(target - num) {
return true
}
set.insert(num)
}
return false
}
如果把題目稍微修改下，變?yōu)?/p>
給定一個整型數(shù)組中有且僅有兩個數(shù)字之和等于目標值值纱，求兩個數(shù)字在數(shù)組中的序號
思路與上題基本類似鳞贷，但是為了方便拿到序列號，我們采用字典虐唠，時間復雜度依然是O(n)搀愧。代碼如下。
func twoSum(nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
} else {
dict[num] = i
}
}
fatalError("No valid output!")
}
字符串
字符串在算法實戰(zhàn)中極其常見疆偿。在Swift中咱筛，字符串不同于其他語言（包括Objective-C），它是值類型而非引用類型杆故。首先還是列舉一下字符串的通常用法：
// 字符串和數(shù)字之間的轉(zhuǎn)換
let str = "3"
let num = Int(str)
let number = 3
let string = String(num)
// 字符串長度
let len = str.count
// 訪問字符串中的單個字符迅箩，時間復雜度為O(1)
let char = str[str.index(str.startIndex, offsetBy: n)]
// 修改字符串
str.remove(at: n)
str.append("c")
str += "hello world"
// 檢測字符串是否是由數(shù)字構(gòu)成
func isStrNum(str: String) -> Bool {
return Int(str) != nil
}
// 將字符串按字母排序(不考慮大小寫)
func sortStr(str: String) -> String {
return String(str.sorted())
}
下面是本篇的精華所在，我們來一起看一道以前的Google面試題处铛。
Given an input string, reverse the string word by word.
A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
這道題目一看好簡單饲趋，不就是翻轉(zhuǎn)字符串的翻版嗎？這種方法有以下兩個問題
- 每個單詞長度不一樣
- 空格需要特殊處理
這樣一來代碼寫起來會很繁瑣而且容易出錯罢缸。不如我們先實現(xiàn)一個字符串翻轉(zhuǎn)的方法。
fileprivate func _reverse<T>(_ chars: inout [T], _ start: Int, _ end: Int) {
var start = start, end = end
while start < end {
_swap(&chars, start, end)
start += 1
end -= 1
}
}
fileprivate func swap<T>(_ chars: inout [T], _ p: Int, _ q: Int) {
(chars[p], chars[q]) = (chars[q], chars[p])
}
有了這個方法投队，我們就可以實行下面兩種字符串翻轉(zhuǎn)：
- 整個字符串翻轉(zhuǎn)枫疆，"the sky is blue" -> "eulb si yks eht"
- 每個單詞作為一個字符串單獨翻轉(zhuǎn)，"eulb si yks eht" -> "blue is sky the"
整體思路有了敷鸦，我們就可以解決這道問題了
func reverseWords(s: String?) -> String? {
guard let s = s else {
return nil
}
var chars = Array(s), start = 0
_reverse(&chars, 0, chars.count - 1)
for i in 0 ..< chars.count {
if i == chars.count - 1 || chars[i + 1] == " " {
_reverse(&chars, start, i)
start = i + 2
}
}
return String(chars)
}
時間復雜度還是O(n)息楔，整體思路和代碼簡單很多。
總結(jié)
Swift中數(shù)組扒披、字符串值依、集合以及字典是最基本的數(shù)據(jù)結(jié)構(gòu)，但是圍繞這些數(shù)據(jù)結(jié)構(gòu)的問題層出不窮碟案。幸運的是解決方法也并不是千變?nèi)f化愿险、高深莫測，大家做好相應(yīng)的積累即可价说。下期我們講鏈表辆亏。
