找出两个只出现了一次的数字(利用异或)

101 阅读 0 评论 67 点赞

我是靠谱客的博主清新缘分，这篇文章主要介绍找出两个只出现了一次的数字(利用异或)，现在分享给大家，希望可以做个参考。

题目描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

输入：

输入的第一行包括一个整数N(1<=N<=1000)。
接下来的一行包括N个整数。

输出：

可能有多组测试数据，对于每组数据，
找出这个数组中的两个只出现了一次的数字。
输出的数字的顺序为从小到大。

样例输入：

复制代码

1
2
6
2 3 9 3 7 2

样例输出：

复制代码

1
7 9

复制代码

1
Code:

复制代码

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int arr[1010];
    int n;
    vector<int> answer;
    while(scanf("%d",&n)!=EOF){
        answer.clear();
        for(int i=0;i<n;++i){
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+n);
        if(arr[0]^arr[1])
            answer.push_back(arr[0]);
        if(arr[n-1]^arr[n-2])
            answer.push_back(arr[n-1]);
        if(answer.size()==2){
           sort(answer.begin(),answer.end());
           printf("%d %dn",answer[0],answer[1]);
        }else{
            for(int i=1;i<=n-2;++i){
                if(arr[i]^arr[i-1]&&arr[i]^arr[i+1])
                    answer.push_back(arr[i]);
                if(answer.size()==2)
                    break;
            }
            sort(answer.begin(),answer.end());
            printf("%d %dn",answer[0],answer[1]);
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1256
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:760 ms
    Memory:1024 kb
****************************************************************/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int arr[1010];
    int n;
    vector<int> answer;
    while(scanf("%d",&n)!=EOF){
        answer.clear();
        for(int i=0;i<n;++i){
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+n);
        if(arr[0]^arr[1])
            answer.push_back(arr[0]);
        if(arr[n-1]^arr[n-2])
            answer.push_back(arr[n-1]);
        if(answer.size()==2){
           sort(answer.begin(),answer.end());
           printf("%d %dn",answer[0],answer[1]);
        }else{
            for(int i=1;i<=n-2;++i){
                if(arr[i]^arr[i-1]&&arr[i]^arr[i+1])
                    answer.push_back(arr[i]);
                if(answer.size()==2)
                    break;
            }
            sort(answer.begin(),answer.end());
            printf("%d %dn",answer[0],answer[1]);
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1256
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:760 ms
    Memory:1024 kb
****************************************************************/