- // 面试题 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;
- }
测试代码
分析: 需要想到异或的性质.
详情见
- 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);
- }
- };
牛客网提交代码
来源: http://www.bubuko.com/infodetail-3497622.html