题目:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路:
如果一个数组中只有一个数字只出现了一次,那么将数组中的所有数字依次异或得到的即位该值
当数组中有两个出现一次的数字时,需要将数组分为两部分,再用上述办法找出两个数字
此时如果将整个数组异或,最终得到的是这两个不同的数字异或之后的结果;在异或结果中找到最右边的1(表示这两个数字中有1个该位为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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { int len = data.size(); if(len < 2) return; int one_or = 0; for(int i = 0; i < len; i++) one_or ^= data[i]; int one_index = FindIndex(one_or); /*---根据one_index位是不是1将数组分为两部分---*/ for(int i = 0; i < len; i++) { if(IndexIsOne(data[i], one_index)) *num1 ^= data[i]; else *num2 ^= data[i]; } } /*---寻找二进制中最右边的1所在的位置---*/ int FindIndex(int one_or) { int idx = 0; while(((one_or & 1) == 0) && (idx < 8 * sizeof(int))) { one_or = one_or >> 1; idx++; } return idx; } /*---判断某一位是不是1---*/ bool IndexIsOne(int num, int idx) { num = num >> idx; return (num & 1); } }; /*------直接将上边的过程合并----*/ class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int len = nums.size(); int temp = 0; for(int i = 0; i < len; i++) temp ^= nums[i]; int mask = 1; while((mask & temp) == 0) mask = mask << 1; int num1 = 0; int num2 = 0; for(int i = 0; i < len; i++) { if(nums[i] & mask) num1 ^= nums[i]; else num2 ^= nums[i]; } vector<int> result; result.push_back(num1); result.push_back(num2); return result; } };
最后
以上就是雪白舞蹈最近收集整理的关于数组中只出现一次的数字 I(C++)(其他数字出现两次)的全部内容,更多相关数组中只出现一次的数字内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复