算法1
(排序) $O(n\log n)$
对原数组进行排序,然后检验每一个数值是否与其下标相等即可。
C++ 代码
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::map;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
sort(a.begin(), a.end());
vector<int> b(n);
iota(b.begin(), b.end(), 1);
cout << (a == b ? "Yes\n" : "No\n");
return 0;
}
算法2
(STL) $O(n\log n)$
可以用 std::set
来对原数组进行去重,然后检验去重后的大小与原数组的大小关系。
C++ 代码
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::set;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
set<int> s;
rep(i, n) s.insert(a[i]);
cout << (s.size() == n ? "Yes\n" : "No\n");
return 0;
}