牛客 小米 找出数组中只出现1次的两个数A,B 位运算经典题

题目描述
一组带数字编号的球里除了两个编号之外，其它的编号都出现了两次。
请写程序找出这两个只出现一次的编号。要求时间复杂度是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 = 01000110
80 = 01010000
90 = 01011010
60 = 00111100
70 = 01000110
80 = 01010000
90 = 01011010
50 = 00110010

---

全部xor后
xor = 00001110

因为xor的最末尾1是倒数第2位,

我们把

• 所有倒数第2位为1的归为一组用来亦或 得到ansA
• 所有倒数第2位为0的归为一组用来亦或 得到ansB

取最末尾1的位置用lowbit函数,

$lowbit$lowbit函数

• 树状数组常用
• $lowbit(x) = x \& (-x)$lowbit(x)=x&(−x)
• 因为计算机用补码存取二进制数，而负数的补码为反码+1，举个例子
  假如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;
}