谁替换了谁:找出数组中缺失的数和重复的数
谁替换了谁:找出数组中缺失的数和重复的数
题目描述: 有 N 个不同的数,分别是 1 到 N,在随机打乱顺序的过程中,出现了一点小误差,其中一个数换成了另一个数。请你找出谁替换了谁,要求时间复杂度是 O(N),辅助空间 O(1),这意味不能使用数组、map、set、vector 等。
输入: N 个数 ai(1<=ai<=N),其中缺了一个,而又有一个数出现了 2 次,其它都出现了 1 次,数之间有一个空格。(N<2000)
输出: 两个整数 a 和 b(a 是缺的哪一个,b 是出现两次的那一个),中间有一个空格,没有回车
输入样例: 2 3 4 1 3 6
输出样例: 5 3
完整的代码内容:
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a;
int i=1;
int temp;
int a1=0,a2=0;
while(cin>>a){
if(a==i){
i++;
}else{
temp=a;
a1=i;
i++;
}
}
i=1;
while(i<=a){
a2^=i;
i++;
}
i=1;
while(i<=a-1){
temp^=i;
i++;
}
a2^=temp;
cout<<a1<<' '<<a2<<endl;
return 0;
}
原文地址: https://www.cveoy.top/t/topic/ntKf 著作权归作者所有。请勿转载和采集!