题目描述
一组带数字编号的球里除了两个编号之外,其它的编号都出现了两次。
请写程序找出这两个只出现一次的编号。要求时间复杂度是O(n),空间复杂度是O(1)。
输入描述:
整形数组
长度不超过1000000
输出描述:
输出数组中2个只出现了一次的数
先输出较小的数
示例1
输入
复制
1
2
3
4
5
2
3
4
5
6
输出
复制
1 6
一组带数字编号的球,其中有两个编号只出现了一次,把它们找出来例如 : [ 2, 3, 4, 5, 2, 3, 4, 5, 7, 8] 则 A=7, B=8
假设数组为
70 = 0100011
0
80 = 01010000
90 = 0101101
0
60 = 00111100
70 = 0100011
0
80 = 01010000
90 = 0101101
0
50 = 0011001
0
全部xor后
xor = 0000111
0
因为xor的最末尾1
是倒数第2
位,
我们把
2
位为1
的归为一组用来亦或
得到ansA2
位为0
的归为一组用来亦或
得到ansB取最末尾1
的位置用lowbit
函数,
函数
ret = 1110 , -ret = 0010 , 所以 i = 0010
代码如下
int A, B, XOR, a[MAXN];
#define lowbit(x) (x & (-x))
void slove() {
while(~scanf("%d ", &m) && ~m) a[++n] = m;
for(int i=1; i<=n; i++) XOR ^= a[i];
XOR = lowbit(XOR); // 取最后一位的 1
// 假设 xor = 110010100
// 则 lowbit(xor)=000000100
for(int i=1; i<=n; i++)
if(XOR & a[i]) A ^= a[i]; //把所有倒数第3位为1的分为一组 xor
else B ^= a[i]; //把所有倒数第3位为0的分为一组 xor
printf("%d %d\n", min(A,B), max(A,B));
}
完整代码(多了很多不必要的演示代码)
#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)2e6+7)
#define ll long long
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
using namespace std;
#define show(x...) \
do { \
cout << "\033[31;1m " << #x << " -> "; \
err(x); \
} while (0)
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
namespace FastIO {
char print_f[105];
void read() { }
void print() { putchar('\n'); }
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth) {
x = 0;
char ch = getchar();
ll f = 1;
while (!isdigit(ch)) {
if (ch == '-') f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
read(oth...);
}
template <typename T, typename... T2>
inline void print(T x, T2... oth) {
ll p3=-1;
if(x<0) putchar('-'), x=-x;
do{
print_f[++p3] = x%10 + 48;
} while(x/=10);
while(p3>=0) putchar(print_f[p3--]);
putchar(' ');
print(oth...);
}
} // namespace FastIO
using FastIO::print;
using FastIO::read;
int n, m, Q, K;
string num_parse(int a, int b, string& aline) { //把a进制的str转成b进制的str
vector<int> num;
string bline;
for(auto c : aline) {
if(c >= '0' && c<='9') num.push_back(c - '0');
else if(c >= 'A' && c <= 'Z') num.push_back(c - 'A' + 10);
else if(c >= 'a' && c <= 'z') num.push_back(c - 'a' + 36);
}
std::reverse(num.begin(), num.end());
vector<int> res;
while(num.size()) { //当商为不为0时就循环
int r = 0; //r是余数
for(int i=num.size()-1; i>=0; i--) { //模拟b进制除法
num[i] += r * a;
r = num[i] % b;
num[i] /= b;
}
res.push_back(r);
while(num.size() && num.back()==0) num.pop_back();
}
for(auto c : res) {
if(c <= 9) bline += char(c+'0');
else if(c >= 10 && c <= 35) bline += char(c+'A'-10);
else if(c >= 36 && c <= 61) bline += char(c+'a'-36);
}
reverse(bline.begin(), bline.end());
return bline;
}
string tobin(int x) {
string tmp = std::to_string(x);
string str = num_parse(10, 2, tmp);
reverse(str.begin(), str.end());
while(str.size() < 8) str.push_back('0');
reverse(str.begin(), str.end());
return str;
}
void ys() {
vector<int> vec = { 70, 80, 90, 60, 70, 80, 90, 50 };
for(auto x : vec) {
string str = tobin(x);
printf(" %d = %s\n", x, str.data());
}
printf("\nxor = %s\n", tobin((50^60)).data());
}
int A, B, XOR, a[MAXN];
#define lowbit(x) (x & (-x))
void slove() {
while(~scanf("%d ", &m) && ~m) a[++n] = m;
for(int i=1; i<=n; i++) XOR ^= a[i];
XOR = lowbit(XOR); // 取最后一位的 1
// 假设 xor = 110010100
for(int i=1; i<=n; i++)
if(XOR & a[i]) A ^= a[i]; //把所有倒数第3位为1的分为一组 xor
else B ^= a[i]; //把所有倒数第3位为0的分为一组 xor
printf("%d %d\n", min(A,B), max(A,B));
}
int main() {
#ifdef debug
freopen("test", "r", stdin);
// freopen("out_main", "w", stdout);
clock_t stime = clock();
#endif
ys(); //演示函数
slove();
#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}