Swift 算法实战之路：数组，字符串，集合，与字典

2016-05-22 本文已影响4976人故胤道长

上次讲解了基本的语法和一些Swift的小技巧。这期我们来看几个最基本的数据结构：数组，字符串，集合和字典。

数组

数组是最基本的数据结构。Swift中改变了以前Objective-C时代NSMutableArray和NSArray分开的做法，统一到了Array唯一的数据结构。虽然看上去就一种数据结构，其实它的实现有三种：

ContiguousArray<Element>：效率最高，元素分配在连续的元素上。如果数组是值类型（栈上操作），Swift会自动调用Array的这种实现；如果注重效率，推荐声明这种类型，尤其是在大量元素是类时，这样做效果会很好。
Array<Element>：会自动桥接到 Objective-C 中的 NSArray，如果是值类型，其性能与ContiguousArray无差别。
ArraySlice<Element>：它不是一个新的数组。只是一个片段，内存上与原数组享用同一区域。

下面是数组最基本的一些运用。

// 声明一个不可修改的数组
let nums = [1, 2, 3]
let nums = [Int](repeating: 0, count: 5)

// 声明一个可以修改的数组
var nums = [3, 1, 2]
// 增加一个元素
nums.append(4)
// 对原数组进行升序排序
nums.sort()
// 对原数组进行降序排序
nums.sort(by: >)
// 将原数组除了最后一个以外的所有元素赋值给另一个数组
let anotherNums = Array(nums[0 ..< nums.count - 1])

不要小看这些简单的操作：数组可以依靠它们实现更多的数据结构。Swift虽然不像Java中有现成的队列和栈，但我们完全可以用数组配合最简单的操作实现这些数据结构，下面就是用数组实现栈的示例代码。

// 用数组实现栈
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
    }
  }
}

最后特别强调一个操作：reserveCapacity()。它用于为原数组预留空间，防止数组在增加和删除元素时反复申请内存空间或是创建新数组，特别适用于创建和removeAll()时候进行调用，为整段代码起到提高性能的作用。

字典和集合

这两个数据结构经常使用的原因在于，查找数据的时间复杂度为O(1)。一般字典和集合要求它们的Key都必须遵守Hashable协议，Cocoa中的基本数据类型都满足这一点；自定义的class需要实现Hashable，而又因为Hashable是对Equable的扩展，所以还要重载 == 运算符。

下面是关于字典和集合的一些实用操作：

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)

// 用字典和高阶函数计算字符串中每个字符的出现频率
Dictionary("hello".map { ($0, 1) }, uniquingKeysWith: +)

集合和字典在实战中经常与数组配合使用，请看下面这道算法题：

给一个整型数组和一个目标值，判断数组中是否有两个数字之和等于目标值

这道题是传说中经典的2Sum，我们已经有一个数组记为nums，也有一个目标值记为target，最后要返回一个Bool值。
最粗暴的方法就是每次选中一个数，然后遍历整个数组，判断是否有另一个数使两者之和为target。这种做法时间复杂度为O(n^2)。
采用集合可以优化时间复杂度。在遍历数组的过程中，用集合每次保存当前值。假如集合中已经有了目标值减去当前值，则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为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
}

如果把题目稍微修改下，变为

给定一个整型数组中有且仅有两个数字之和等于目标值，求两个数字在数组中的序号

思路与上题基本类似，但是为了方便拿到序列号，我们采用字典，时间复杂度依然是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!")
}

字符串

字符串在算法实战中极其常见。在Swift中，字符串不同于其他语言（包括Objective-C），它是值类型而非引用类型。首先还是列举一下字符串的通常用法：

// 字符串和数字之间的转换
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"

// 检测字符串是否是由数字构成
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?

这道题目一看好简单，不就是翻转字符串的翻版吗？这种方法有以下两个问题

每个单词长度不一样
空格需要特殊处理

这样一来代码写起来会很繁琐而且容易出错。不如我们先实现一个字符串翻转的方法。

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])
}

有了这个方法，我们就可以实行下面两种字符串翻转：

整个字符串翻转，"the sky is blue" -> "eulb si yks eht"
每个单词作为一个字符串单独翻转，"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)，整体思路和代码简单很多。

总结

Swift中数组、字符串、集合以及字典是最基本的数据结构，但是围绕这些数据结构的问题层出不穷。幸运的是解决方法也并不是千变万化、高深莫测，大家做好相应的积累即可。下期我们讲链表。

Swift 算法实战之路：数组，字符串，集合，与字典

数组

字典和集合

字符串

总结

猜你喜欢

热点阅读