我是靠谱客的博主 哭泣期待,这篇文章主要介绍面试题56:数组中数字出现的次数,现在分享给大家,希望可以做个参考。

题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。要求时间复杂度O(n),空间复杂度O(1).
两不同数字异或为1 ,按位是否为1分成两组,则各只含一个不同数字。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { int len = data.size(); if(data.empty() || len < 2) return; int resXOR = 0; for(int i = 0; i < len; ++i) resXOR ^= data[i];//找出两个不同数字的异或结果 int indexOf1 = findFirstBitIs1(resXOR); *num1 = *num2 = 0; for(int j = 0; j < len; ++j) { if(isBit1(data[j], indexOf1)) *num1 ^= data[j]; else *num2 ^= data[j]; } } int findFirstBitIs1(int num)//找到右边起的第一个值为1的位 { int indexBit = 0; while((num & 1) == 0 && (indexBit < 8 * sizeof(int))) { num = num >> 1; ++ indexBit; } return indexBit; } bool isBit1(int num, int index)//判断num右起第index位是否为1 { num = num >> index; return (num & 1); } };

最后

以上就是哭泣期待最近收集整理的关于面试题56:数组中数字出现的次数的全部内容,更多相关面试题56:数组中数字出现内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(86)

评论列表共有 0 条评论

立即
投稿
返回
顶部