谁替换了谁:找出数组中缺失的数和重复的数

题目描述: 有 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 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录