算法面试题04 - 出现一次的数字

请实现一个函数，给定一个整数数组，找出数组中第一个只出现一次的数字。

【示例】
给定数组[2, 2, 1]，返回1；给定数组[4, 1, 2, 1, 2]，返回4。

答案

func findFirstUniqueElement(_ arr: [Int]) -> Int? {
    var map = [Int: Int]()
    for value in arr {
        if map[value] == nil {
            map[value] = 1
        } else {
            map[value]! += 1
        }
    }
    for (key, value) in map {
        if value == 1 {
            return key
        }
    }
    return nil
}
  
// 测试用例
print(findFirstUniqueElement([2, 2, 1]) ?? "")  // 输出：1
print(findFirstUniqueElement([4, 1, 2, 1, 2]) ?? "")  // 输出：4

知识点详解：

1. 字典(Dictionary)的使用

• 创建字典变量来存储数字和出现次数
• 根据key设置和访问value
• 遍历字典的key和value

2. 数组的遍历

• 使用for-in循环遍历数组
• 访问数组元素并更新字典

3. 算法

• 使用字典进行统计计数
• 找到满足特定条件的键值

算法思路

1. 使用字典dict来记录每个数字出现的次数。
2. 遍历数组nums，将每个数字出现的次数记录在dict中。
3. 再遍历dict，找出只出现一次的数字，也就是字典value为1的key。
4. 如果不存在只出现一次的数字，返回-1。

时间复杂度分析

算法中有两次遍历数组的循环，所以时间复杂度与数组长度n线性相关，是O(n)。
第一层for循环需要遍历一次数组，复杂度是O(n)。
第二层for循环需要遍历字典，字典中的元素最多和数组元素个数n一样多，复杂度也是O(n)。
总时间复杂度为两部分之和，即O(n) + O(n)，仍然是O(n)。

空间复杂度分析

算法中使用了一个字典来存储每个元素出现的次数，字典最多需要存储n个数字，所以额外空间复杂度为O(n)。
数组本身占用的空间可以看作是输入的一部分，不考虑在空间复杂度分析中。
所以总空间复杂度为 O(n)。

BTW

感谢各位简友的宝贵时间与意见！文章难免有疏漏或错误，如有涉及不当之处，还望能够提出宝贵意见。感激不尽！