给出数组a求出他是否能凑出1到n写出c++代码
时间: 2024-09-15 20:14:46 浏览: 43
C++ 实现求小于n的最大素数的实例
5星 · 资源好评率100%
要判断一个整数数组`a`能否通过选择其中的元素组成从1到`n`的所有整数序列,你可以使用哈希集合(HashSet)来检查是否存在缺失的数字。下面是C++代码的一个示例:
```cpp
#include <iostream>
#include <unordered_set>
using namespace std;
bool canMakeArray(vector<int>& a, int n) {
unordered_set<int> nums(a.begin(), a.end()); // 使用哈希集存储数组中的数字
// 遍历1到n,如果遇到nums中不存在的数字,则返回false
for (int i = 1; i <= n; ++i) {
if (nums.find(i) == nums.end()) { // 如果找不到数字i,说明无法组成序列
return false;
}
}
// 没有发现缺失的数字,所以可以组成序列
return true;
}
int main() {
vector<int> a;
cin >> a.size(); // 获取数组长度
a.resize(a.size());
for (int& num : a) {
cin >> num;
}
int n;
cin >> n;
bool result = canMakeArray(a, n);
cout << (result ? "可以" : "不可以") << endl;
return 0;
}
```
在这个代码中,`canMakeArray`函数首先将数组转换成哈希集合`nums`,然后逐个检查从1到n的数字,如果遇到集合中没有的数字就立即返回`false`。如果循环结束后都没有找到缺失的数字,说明数组`a`能够组成从1到`n`的序列,返回`true`。
阅读全文