codevsthing

2018-01-15 13:34:58


  1. 给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。

  2. 给你n个数,其中有且仅有两个数出现了奇数次,其余的数都出现了偶数次。用线性时

ans::

  1. 从头到尾异或一遍,最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质:两次异或同一个数,结果不变。再考虑到异或运算满足交换律,先异或和后异或都是一样的,因此这个算法显然正确。

  2. 从头到尾异或一遍,你就得到了需要求的两个数异或后的值。这两个数显然不相等,异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位,然后把所有这n个数分成两类,在那一位上是0的分成一类,在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

1

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int main(){
    ios::sync_with_stdio;
    int n=read(),x=read(),y;
    for(int i=1;i<n;++i){
        y=read();
        x^=y;
    }
    cout<<x;
    return 0;
}
2.............