找出奇数个数中唯一出现一次的数

问题描述

 现在有一堆奇数个数字，只有一个出现了一次，其余都出现了偶数次，找出这个数。

解决思路

 如果采用简单遍历的方法统计每一个出现的次数，然后输出次数为1的数，这样有点复杂，时间复杂度为O(n2)。

#include<iostream>
using namespace std;
typedef struct {
    int value;
    int count=;
}Num;
int main() {
    int n;
    Num num[];
    int answer;
        cin >> n;
        while (n %  == ) {
            cout << "请输入奇数：";
            cin >> n;
        }
        for (int i = ;i < n;i++) {
            int flag = ;
            cin >> num[i].value;
            for (int j = ;j < i;j++) {  //循环遍历以前的数
                if (num[j].value == num[i].value) {
                    flag = ;
                    num[j].count++;
                }
            }
            if (flag) {  //若存在相等，则本身也要count++;
                num[i].count++;
            }
        }
        for (int i = ;i < n;i++) {    //找出出现的一次的数
            if (num[i].count == ) {
                answer = num[i].value;
                break;
            }
        }
        cout << answer << endl;
}
           

 如何才能进一步降低时间复杂度呢，这里用到位运算异或的方法，利用数的二进制位解决问题，相同的数字异或的结果是全0二进制数，微观的说，所有偶数个的数的位的值出现偶数次，最后的异或的结果必为0，这样出现一次的数就会使这些位数出现的次数为奇数，所以最后异或的结果就是我们要找的数，时间复杂度为O(1).

异或：1与1、0与0异或为0，而1与0异或为1。

#include<iostream>
using namespace std;
int solve(int num[],int n) {  //异或
    int answer=num[];
    for (int i = ;i < n;i++) {  //循环每次都与结果异或
        answer^=num[i];
    }
    return answer;
}
int main() {
    int n;
    cin >> n;
    int num[];
    while (n %  == ) {
        cout << "请输入奇数:";
        cin >> n;
    }
    for (int i = ;i < n;i++) {
        cin >> num[i];
    }
    int answer = solve(num,n);
    cout << answer << endl;
    cin >> n;
}