// 面试题56（一）：数组中只出现一次的两个数字 // 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序 // 找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 #include <cstdio> unsigned int FindFirstBitIs1(int num); bool IsBit1(int num, unsigned int indexBit); void FindNumsAppearOnce(int data[], int length, int* num1, int* num2) { if (data == nullptr || length < 2) return; int resultExclusiveOR = 0; for (int i = 0; i < length; ++i) //自反性, A XOR B XOR B = A XOR 0 = A resultExclusiveOR ^= data[i]; //因为有两个不同的数, 因此其结果二进制中必定有一位为1 //其中一个数字此位为1, 另一个必定为0. 1 XOR 0 = 1 unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); *num1 = *num2 = 0; for (int i = 0; i < length; ++i) { if (IsBit1(data[i], indexOf1)) //因此将原数组分为两组, 此位为1 *num1 ^= data[i]; else //此位为0 *num2 ^= data[i]; } } // 找到num从右边数起第一个是1的位 unsigned int FindFirstBitIs1(int num) { unsigned int index = 0; while (((num & 1) == 0) //当前位为1跳出 && (index < 8 * sizeof(int))) //不会超出int { num = num >> 1; ++index; } return index; } // 判断数字num的第indexBit位是不是1 bool IsBit1(int num, unsigned int indexBit) { num = num >> indexBit; return (num & 1); }
// ====================测试代码==================== void Test(const char* testName, int data[], int length, int expected1, int expected2) { if (testName != nullptr) printf("%s begins: ", testName); int result1, result2; FindNumsAppearOnce(data, length, &result1, &result2); if ((expected1 == result1 && expected2 == result2) || (expected2 == result1 && expected1 == result2)) printf("Passed.\n\n"); else printf("Failed.\n\n"); } void Test1() { int data[] = { 2, 4, 3, 6, 3, 2, 5, 5 }; Test("Test1", data, sizeof(data) / sizeof(int), 4, 6); } void Test2() { int data[] = { 4, 6 }; Test("Test2", data, sizeof(data) / sizeof(int), 4, 6); } void Test3() { int data[] = { 4, 6, 1, 1, 1, 1 }; Test("Test3", data, sizeof(data) / sizeof(int), 4, 6); } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); return 0; }
分析：需要想到异或的性质。
详情见https://www.cnblogs.com/suoloveyou/archive/2012/04/25/2470292.html
class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { int length = data.size(); if (data.empty() || length < 2) return; int Xor = 0; for (int i = 0; i < length; ++i) Xor ^= data[i]; unsigned int indexOf1 = FindIndexOf1(Xor); *num1 = *num2 = 0; for (int i = 0; i < length; ++i) { if (IsBit1(data[i], indexOf1)) *num1 ^= data[i]; else *num2 ^= data[i]; } } unsigned int FindIndexOf1(int num) { unsigned int index = 0; while (((num & 1)== 0) && index < 8 * sizeof(int)) { num = num >> 1; ++index; } return index; } bool IsBit1(int num, unsigned int index) { num = num >> index; return (num & 1); } };
原文：https://www.cnblogs.com/ZSY-blog/p/12658576.html
