题目描述：

  1. 一个整型数组里只有一个数字出现里只出现一次，其他数字都出现两次，请写出程序找出只出现一次的数字。
  2. 一个整型数组里除了两个数字之外，其他的数字都出现两次。请写出程序找出这两个只出现一次的数字。

方法一：
对两题都适用。
利用字典(map)，map的key是数组中的数字，value是此数字出现的次数。需要遍历两次，第一次遍历数组，初始化字典，第二次遍历字典找出两个只出现一次的值。

  2. class Solutions {
  3.     func findNumbers(_ inputNums: [Int]) -> Int {
  4.         var result: Int = 0
  5.         var map: [Int: Int] = [:]
  6.         for item in inputNums {
  7.             if let value = map[item] {
  8.                 map[item] = value + 1
  9.             }
  10.             else {
  11.                 map[item] = 1
  12.             }
  13.         }
  14.         for (item, value) in map {
  15.             if value == 1 {
  16.                 result = item
  17.                 break
  18.             }
  19.         }
  20.         return result
  21.     }
  22. }
  24. let num = Solutions().findNumbers([1, 1, 2])
  25. print(num)

方法二：
限定条件：时间复杂度为O(n)，空间复杂度为O(1)，这样的话，方法一就不满足了。

来复习下位运算中操作符：异或：两个数字异或之后相同为0，一个数字和0异或还是他本身。
异或的运算法则：

  1. a ^ a = 0
  2. a ^ 0 = a
  3. a ^ b = b ^ a
  4. a ^ b ^ a = b
  6. // 若x是二进制数0101，y是二进制数1011
  7. x ^ y = 1110
  8. // 相同为0，不同为1

所以，对题目1来说，当只有一个数出现一次时，把数组中所有元素依次异或，最后的结果就是落单的数。

  1. class Solutions {
  2.     func findNumbers(_ inputNums: [Int]) -> Int {
  3.         var result: Int = 0
  4.         for item in inputNums {
  5.             result = result ^ item
  6.         }
  7.         return result
  8.     }
  9. }
  11. let num = Solutions().findNumbers([1, 1, 2])
  12. print(num)

再来看题目2，一个数组中有两个数字只出现了一次的情况，假设是A、B两个数字只出现一次，最后的结果肯定是A和B异或的结果，将结果转为二进制，二进制中的1代表的是A和B不同的位。取到A和B中第一个不同的位（即第一个1所在的位数），例如第二位，然后按二进制第二位为1把原数组进行分组。然后会有两个数组：由于是A、B异或结果为1，所有A、B的二进制的第二位肯定不一样，即A、B会分在不同的数组里。而且对于同一组来说，同一组里的其他元素肯定都是偶数出现的，因为只有两个数字只出现了一次。所有最终对于每一组来说，就有变成了题目1.

  2. class Solutions {
  3.     func isBit1(target: Int, index: Int) -> Bool {
  4.         return ((target >> index) & 1) == 1
  5.     }
  7.     func findNumbers(_ inputNums: [Int]) -> [Int] {
  8.         var nums1: [Int] = [] // 存储第X位是1的数组
  9.         var nums2: [Int] = [] // 存储第X位非1的数组
  10.         if inputNums.count == 2 {
  11.             nums1.append(inputNums[0])
  12.             nums2.append(inputNums[1])
  13.         }
  15.         var tempResult = 0 // tempResult结果肯定是只出现一次的两个数的异或结果
  16.         for item in inputNums {
  17.             tempResult = tempResult ^ item
  18.         }
  19.         // 遍历tempResult的二进制，找到第一个为1的位
  20.         let tempStr = String(tempResult, radix: 2)
  21.         var firstIndex = 0
  22.         for charS in tempStr {
  23.             if charS == "1" {
  24.                 break
  25.             }
  26.             firstIndex += 1
  27.         }
  29.         var firstValue = 0
  30.         var secondValue = 0
  31.         for item in inputNums {
  32.             if isBit1(target: item, index: firstIndex) {
  33.                 firstValue = firstValue ^ item
  34.             }
  35.             else {
  36.                 secondValue = secondValue ^ item
  37.             }
  38.         }
  40.         return [firstValue, secondValue]
  41.     }
  42. }
  44. let num = Solutions().findNumbers([1, 1, 2, 3])
  45. print(num)