题目
一个整型数组里除了两个数字之外，，其他的数字都是出现了两次。请写出程序找出这两个只出现了一次的数字。要求时间复杂度是O(n), 空间复杂度是O(1)。
题解
tip1：如果该数组A中只有一个数字出现了一次，其他的数字都出现了两次，那么求出该数字就很简单，其值就是 A[0] ^ A[1] ^ … ^ A[n-1] 因此就需要想办法，将问题转换为tip1里的问题场景。 tip2：将题目中的数组的每个数字都异或，求得值为x，那么实际上x就是该数组中那两个仅出现了一次的数字的异或值。 假设x的第k为1，那么将原数组中所有的数字按照第k位是否为1，进行划分为两个数组。 然后对两个数组，分别实行tip1的解法即可。因为每个子数组中，都存在一个仅出现一次的数字，其余的数字都出现两次。
代码;class Solution {public:// A is an array, whose length is nvoid solve(int A[], int n) {int x = 0;for (int i = 0; i < n; i++) x ^= A[i];// assert x != 0int lowestBit = x – (x & (x-1));int left = 0, right = n-1;while (left <= right) {while (left <= right && (A[left]&lowestBit) == 0) left++;while (left <= right && (A[right]&lowestBit) == 1) right–;if (left <= right) swap(A, left, right);}int x1 = 0, x2 = 0;for (int i = 0; i < left; i++) x1 ^= A[i];for (int i = left; i < n; i++) x2 ^= A[i];printf(“x1:%d, x2:%d\n”, x1, x2);}void swap(int A[], int i, int j) {int tmp = A[i];A[i] = A[j];A[j] = tmp;}}; int main() {int A[] = {2, 3, 2, 4, 3, 5, 6, 7, 7, 6};Solution solution;solution.solve(A, sizeof(A)/sizeof(int));return 0;}
怠惰是贫穷的制造厂。
