能帮忙看看这段代码哪里有问题吗?
参考:(14条未读通知) 有趣的数字__牛客网 (nowcoder.com)
题目:小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,相差最小的有多少对呢?相差最大呢?
思路:(注:参考他人的)
第一遍没看懂题目,(智商余额不足了。。。)
看明白之后,感觉挺简单,直接O(n^2)就完了,但是好像O(n^2)超时。
改进后思路:
1.先排序
特殊情况:如果排完序之后发现数组中所有数都相同,直接输出结果
结果为:差最大个数 = 差最小个数 = (n * (n-1))/2;(两两组合)
2.统计数组中每种数字的个数(这里用的map)
3.计算差最小个数
3.1.如果数组中没有重复数字,说明最小差不为0,最小差肯定是数组中相邻两个数的差
因此,遍历一边数组,计算并统计最小差。
3.2.如果数组中有重复数字,说明最小差是0,此时,遍历一边map,数字个数不为0的
数字会产生最小差0,利用公式计算即可
4.计算差最大个数
只有一种情况,最大值与最小值的两两组合,即最大值个数 * 最小值个数
代码:
#include <bits/stdc++.h>
using namespace std;
void MaxAndMinCnt(vector<int>& num, int& max_cnt, int& min_cnt){
if(num.size() == 2){
max_cnt = 1;
min_cnt = 1;
return;
}
bool flag = true;
map<int, int> n_c;
sort(num.begin(), num.end());
if(num[0] == num[num.size() - 1]){
min_cnt = max_cnt = num.size() * (num.size() - 1);
return;
}
// 计算最小个数
for(int i = 0; i < num.size() - 1; i++){
if(n_c.find(num[i]) != n_c.end()){
n_c[num[i]]++;
}
else{
n_c[num[i]] = 1;
}
if(flag && n_c[num[i]] > 1)
flag = false;
}
if(!flag){// 有0情况
for(map<int, int>::iterator it = n_c.begin(); it != n_c.end(); it++){
int v = it->second;
if(v > 1){
min_cnt += ((it->second * (it->second - 1))) / 2;
}
}
}
else{// 无0情况,全不同
int min_num = abs(num[1]- num[0]);
min_cnt = 1;
for(int i = 1; i < num.size() - 1; i++){
int v = abs(num[i + 1] - num[i]);
if(v == min_num){
min_cnt++;
}
else if(v < min_num){
min_num = v;
min_cnt = 1;
}
}
}
// 计算最大个数
int front = count(num.begin(), num.end(), num[0]);
int back = count(num.rbegin(), num.rend(), num[num.size() - 1]);
max_cnt = front * back;
}
int main(){
int n, v, min_cnt = 0, max_cnt = 0;// 差最小个数,差最大个数
vector<int> num;
while(cin>>n){
num.clear();
num.resize(n);
min_cnt = 0;
max_cnt = 0;
for(int i = 0; i < n; i++){
cin>>v;
num[i] = v;
}
MaxAndMinCnt(num, max_cnt, min_cnt);
cout<<min_cnt<<" "<<max_cnt<<endl;
}
return 0;
}
测试结果:
有一个结果总少2,另一个总少1.
1.小错误:在计算最小差个数的时候,当没有重复数字的时候,初始的最小差应该是min_num = abs(num[1]- num[0]) ;
,而不是min_num = abs(num[0]- num[num.size()-1]);
。
2.改进:可以使用unordered_map
替换map
,因为它在大多数情况下比map
更快。
3.改进:可以使用auto
和范围循环来简化代码,如for(auto& [num, freq] : n_c)
。
4.改进:可以使用accumulate
函数来计算总数,如min_cnt = accumulate(begin(n_c), end(n_c), 0, [](int a, const auto& p){ return a + p.second * (p.second - 1) / 2; });
。
#include <bits/stdc++.h>
using namespace std;
void MaxAndMinCnt(vector<int>& num, int& max_cnt, int& min_cnt){
if(num.size() == 2){
max_cnt = 1;
min_cnt = 1;
return;
}
bool flag = true;
unordered_map<int, int> n_c;
sort(num.begin(), num.end());
if(num[0] == num[num.size() - 1]){
min_cnt = max_cnt = num.size() * (num.size() - 1) / 2;
return;
}
// 计算最小个数
for(int i = 0; i < num.size() - 1; i++){
if(n_c.find(num[i]) != n_c.end()){
n_c[num[i]]++;
}
else{
n_c[num[i]] = 1;
}
if(flag && n_c[num[i]] > 1)
flag = false;
}
if(!flag){// 有重复数字
min_cnt = accumulate(begin(n_c), end(n_c), 0, [](int a, const auto& p){ return a + p.second * (p.second - 1) / 2; });
}
else{// 无重复数字
int min_num = abs(num[1]- num[0]);
min_cnt = 1;
for(int i = 1; i < num.size() - 1; i++){
int v = abs(num[i + 1] - num[i]);
if(v == min_num){
min_cnt++;
}
else if(v < min_num){
min_num = v;
min_cnt = 1;
}
}
}
// 计算最大个数
int front = count(num.begin(), num.end(), num[0]);
int back = count(num.rbegin(), num.rend(), num[num.size() - 1]);
max_cnt = front * back;
}
int main(){
int n, v, min_cnt = 0, max_cnt = 0;// 差最小个数,差最大个数
vector<int> num;
while(cin>>n){
num.resize(n);
min_cnt = 0;
max_cnt = 0;
for(int i = 0; i < n; i++){
cin>>v;
num[i] = v;
}
MaxAndMinCnt(num, max_cnt, min_cnt);
cout<<min_cnt<<" "<<max_cnt<<endl;
}
return 0;
}