C++算法：查找数组中缺失的两个数字

本文介绍如何使用C++编写算法，查找给定数组中缺失的两个数字。

问题描述：

给定一个包含28个元素的整数数组，元素取值范围是[1,30]，元素值不重复。其中丢失了2个数字，请找出丢失的这两个数。

要求：

如果数组没有28个元素，输出：-1* 如果数组存在相同的元素，输出：-1

算法思路：

检查数组大小和元素范围： 首先，检查给定数组是否包含28个元素，以及所有元素是否都在[1,30]范围内。如果不是，则输出-1，表示输入数组不符合要求。2. 利用无序集合去重： 使用C++标准库中的unordered_set来存储数组元素。由于unordered_set不允许重复元素，我们可以利用它来检查数组中是否存在重复元素。3. 查找缺失数字： 遍历从1到30的所有数字，检查每个数字是否存在于unordered_set中。如果不存在，则说明该数字是缺失的数字，将其添加到missingNumbers向量中。一旦找到两个缺失数字，立即返回结果。

**代码示例：**c++#include #include #include <unordered_set>

std::vector findMissingNumbers(const std::vector& arr) { std::vector missingNumbers;

if (arr.size() != 28) {        missingNumbers.push_back(-1);        return missingNumbers;    }

std::unordered_set<int> distinctNumbers;    for (int num : arr) {        if (num < 1 || num > 30 || distinctNumbers.count(num) > 0) {            missingNumbers.push_back(-1);            return missingNumbers;        }        distinctNumbers.insert(num);    }

for (int i = 1; i <= 30; i++) {        if (distinctNumbers.count(i) == 0) {            missingNumbers.push_back(i);            if (missingNumbers.size() == 2) {                return missingNumbers;            }        }    }

return missingNumbers;}

int main() { std::vector arr = {1, 3, 5, 6, 7, 8, 9, 11, 13, 15, 16, 17, 18, 19, 21, 23, 24, 25, 26, 27, 29, 30, 2, 4, 10, 12, 14, 20};

std::vector<int> missingNumbers = findMissingNumbers(arr);

if (missingNumbers[0] == -1) {        std::cout << '数组大小不对或存在重复元素' << std::endl;    } else {        std::cout << '丢失的两个数字是: ' << missingNumbers[0] << ' 和 ' << missingNumbers[1] << std::endl;    }

return 0;}

代码说明：

findMissingNumbers函数接收一个整数向量作为输入，并返回一个包含两个缺失数字的整数向量。* 代码首先检查输入数组的大小和元素范围，如果不符合要求，则返回{-1}。* 然后，代码使用unordered_set来存储数组元素并检查重复元素。* 最后，代码遍历从1到30的所有数字，查找不在unordered_set中的数字，并将它们添加到missingNumbers向量中。

总结：

本文介绍了一种使用C++查找数组中缺失的两个数字的算法，并提供了详细的代码示例和说明。该算法利用了unordered_set的数据结构来提高效率，并且代码简洁易懂。希望本文能够帮助您理解和解决类似的编程问题。