136. 只出现一次的数字

题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

解题

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        return nums.reduce(0, ^)
    }
}

Swift 中的 reduce 怎样使用 ？

在 Swift 中，reduce 是一种用于将集合（例如数组）的元素合并成单一值的高阶函数。它通过一个初始值和一个合并操作函数将集合中的所有元素合并起来。以下是 reduce 的一般用法：

let array = [1, 2, 3, 4, 5]

// 使用 reduce 将数组元素求和
let sum = array.reduce(0) { (result, element) -> Int in
    return result + element
}

print(sum) // 输出 15

在上面的代码中：

• array.reduce(0) 表示初始值为 0。
• 闭包 (result, element) -> Int in return result + element 是合并操作函数，其中 result 是前一次合并操作的结果（初始值为 0），element 是当前数组元素。闭包的返回值将作为下一次合并操作的 result。

使用更简洁的方式，我们可以将闭包简化为：

let sum = array.reduce(0, +)
print(sum) // 输出 15

下面是几个不同场景下使用 reduce 的例子：

1. 计算数组元素的乘积

let product = array.reduce(1, *)
print(product) // 输出 120

2. 将字符串数组合并成一个字符串

let stringArray = ["Swift", "is", "awesome"]
let combinedString = stringArray.reduce("") { $0 + " " + $1 }

print(combinedString) // 输出 " Swift is awesome"

3. 计算数组元素的最大值

let maxElement = array.reduce(array[0]) { (result, element) -> Int in
    return result > element ? result : element
}

print(maxElement) // 输出 5

4. 将字典的值求和

let dictionary = ["a": 1, "b": 2, "c": 3]

let sumOfValues = dictionary.reduce(0) { (result, pair) -> Int in
    return result + pair.value
}

print(sumOfValues) // 输出 6

reduce 是一个非常强大的工具，可以用来实现多种数据处理操作。通过合理使用 reduce，你可以使代码更加简洁和优雅。

理解什么是“异或”

异或（XOR，exclusive OR）是一种二进制运算，常用于计算机科学和数字逻辑领域。异或运算符对两个二进制位进行比较，如果两个位不同，结果为1；如果两个位相同，结果为0。

具体地，对于两个二进制数 A 和 B，它们的异或运算可以表示为：

A ⊕ B

异或运算的真值表如下：

异或运算的性质

1. 交换律：
   [
   A ⊕ B = B ⊕ A
   ]

2. 结合律：
   [
   (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
   ]

3. 自反性：
   [
   A ⊕ A = 0
   ]

4. 恒等性：
   [
   A ⊕ 0 = A
   ]

异或运算的应用

1. 加密解密：
   异或运算常用于简单的加密解密算法中。例如，如果你想加密一个字符 C，你可以用一个密钥 K 进行异或操作：
   [
   E = C ⊕ K
   ]
   解密时，再次使用相同的密钥进行异或操作：
   [
   C = E ⊕ K
   ]

2. 数据校验：
   异或运算用于生成校验和，以验证数据传输的正确性。例如，TCP/IP 协议中使用异或来生成校验和。

3. 位操作技巧：
   异或运算可以用于交换两个变量而不使用临时变量：

   var a = 5
   var b = 3
   
   a = a ⊕ b
   b = a ⊕ b
   a = a ⊕ b
   
   // 交换后 a = 3, b = 5
   

4. 查找不重复的元素：
   在一个数组中查找唯一不重复的元素：

   let array = [1, 2, 3, 2, 1]
   let uniqueElement = array.reduce(0, ^)
   print(uniqueElement) // 输出 3
   

通过以上这些例子，你可以看到异或运算在计算机科学和日常编程中有着广泛的应用。

Swift 中的“异或”

在 Swift 中，异或（XOR）操作符是 ^。它用于对两个整数进行按位异或运算。

以下是一些在 Swift 中使用异或操作的示例：

基本使用

let a: UInt8 = 0b1100  // 二进制表示的12
let b: UInt8 = 0b1010  // 二进制表示的10

let result = a ^ b     // result 为 0b0110，即 6

print(result)  // 输出 6

在这个例子中：

• a 和 b 是两个 8 位无符号整数。
• a ^ b 进行按位异或运算，结果为 0b0110，即十进制的 6。

使用异或进行加密和解密

可以用异或操作进行简单的加密和解密操作。假设我们有一个字符和一个密钥，通过异或操作加密该字符，再通过相同的密钥解密该字符：

let char: UInt8 = 65  // 字符 'A' 的 ASCII 码
let key: UInt8 = 123  // 任意选择的密钥

let encrypted = char ^ key
print("Encrypted: \(encrypted)")  // 输出加密后的值

let decrypted = encrypted ^ key
print("Decrypted: \(decrypted)")  // 输出 65，解密后的字符 'A'

使用异或交换两个变量的值

异或操作可以用来交换两个变量的值而不需要临时变量：

var x = 5
var y = 3

x = x ^ y
y = x ^ y
x = x ^ y

print("x: \(x), y: \(y)")  // 输出 "x: 3, y: 5"

查找数组中唯一不重复的元素

给定一个数组，其中有一个元素是唯一的，其他元素都是成对出现的，可以用异或操作找到这个唯一不重复的元素：

let array = [1, 2, 3, 2, 1]
let uniqueElement = array.reduce(0, ^)

print("Unique element: \(uniqueElement)")  // 输出 3

在这个例子中，reduce(0, ^) 表示从初始值 0 开始，通过异或操作将数组中的每个元素依次合并。由于相同的元素异或结果为 0，最后剩下的就是唯一不重复的元素。

以上这些示例展示了如何在 Swift 中使用异或操作，以及它在不同场景中的应用。