steven_lv-20180729.md

ARTS Week Five

Algorithm

Count Occurrences

• 先排序
• 用 binary search 找出 key 的开始位置和结束位置相减

  func countOccurrencesOfKey(_ key: Int, inArray a: [Int]) -> Int {
  func leftBoundary() -> Int {
    var low = 0
    var high = a.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] < key {
        low = midIndex + 1
      } else {
        high = midIndex
      }
    }
    return low
  }

  func rightBoundary() -> Int {
    var low = 0
    var high = a.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] > key {
        high = midIndex
      } else {
        low = midIndex + 1
      }
    }
    return low
  }

  return rightBoundary() - leftBoundary()
}

let a = [0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11] // 排过序的，未排序的要先排序

countOccurrencesOfKey(3, inArray: a)  // returns 4