C++高效查找数组中唯一不重复的数字

本文介绍如何使用C++的unordered_map容器高效查找数组中唯一不重复的数字，并提供完整代码示例和时间复杂度分析。

问题描述:

给定一个整数数组，其中只有一个数字出现一次，而其他所有数字都出现两次。要求设计一个高效的算法找到这个唯一不重复的数字。

解决方案:

使用unordered_map容器可以高效地解决这个问题。unordered_map是一种哈希表实现，可以快速地存储和查找键值对。

**代码示例:**cpp#include #include <unordered_map>#include

int findUniqueNumber(const std::vector& arr) { std::unordered_map<int, int> countMap; // 创建一个unordered_map容器

// 统计每个数字出现的次数    for (const auto& num : arr) {        countMap[num]++;    }

// 遍历unordered_map，找到出现次数为1的数字    for (const auto& pair : countMap) {        if (pair.second == 1) {            return pair.first;        }    }

// 没有找到唯一数字，返回一个合适的默认值或者抛出异常    return -1; // 默认返回-1}

int main() { std::vector arr = {2, 4, 6, 4, 2, 8, 6}; // 示例数组

int uniqueNumber = findUniqueNumber(arr);    if (uniqueNumber != -1) {        std::cout << 'The unique number is: ' << uniqueNumber << std::endl;    } else {        std::cout << 'No unique number found.' << std::endl;    }

return 0;}

代码解释:

首先创建一个unordered_map容器，用于存储每个数字和其出现次数的键值对。2. 遍历输入数组，统计每个数字出现的次数，并将结果存储到unordered_map中。3. 遍历unordered_map，找到出现次数为1的数字，即为唯一不重复的数字。4. 如果没有找到唯一数字，则返回一个默认值或抛出异常。

时间复杂度:

该算法的时间复杂度为O(n)，其中n是数组中的元素个数。这是因为我们只需要遍历数组一次即可统计每个数字的出现次数，并且unordered_map的插入和查找操作平均时间复杂度都是O(1)。

总结:

使用unordered_map容器可以高效地解决查找数组中唯一不重复数字的问题。该算法时间复杂度低，实现简单易懂。